Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 求大佬帮助。。 查遍discuss所有数据。。dijkstra+等级枚举

Posted by hanyuweining at 2017-05-16 22:30:53 on Problem 1062
```代码很丑，求轻喷【摊手】

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF=1000000;

int a[101],f[101][101],q[101];
int dist[101],use[101],r[101];
bool p[101];
int n,m;

int dijkstra(int low,int high)
{
int i,b,j,l,x;
memset(dist,0x3f,sizeof(dist));
memset(use,0,sizeof(use));
dist[1]=0;
dist[0]=2147483647;
for(i=1;i<=n;i++)
{
int w=0;
for (int b=1;b<=n;b++)
{
if (!use[b] && (w==-1 || dist[b]<dist[w])&& q[b]>=low && q[b]<=high)
{
w=b;
}
}

if (w==-1)
{
break;
}
use[w]=true;
for (j=1;j<=n;j++)
{
if(f[w][j]!=2147483647&&q[j]>=low&&q[j]<=high)
{
x=dist[j];
dist[j]=min(dist[w]+f[w][j],dist[j]);
if(x!=dist[j]&&a[r[j]]>a[w]&&q[j]>=low&&q[j]<=high)
{
r[j]=w;
}
}
}
}
x=2147483647;
for(i=1;i<=n;i++)
{
if(dist[i]+a[r[i]]<x&&q[i]>=low&&q[i]<=high)
{
x=dist[i]+a[r[i]];
}
}
return x;
}

int main()
{
int i,j,t,v,k;

scanf("%d%d",&m,&n);
for(i=0;i<101;i++)
{
for(j=0;j<101;j++)
{
f[i][j]=2147483647;
}
}
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i],&q[i],&k);
for(j=1;j<=k;j++)
{
scanf("%d%d",&t,&v);
f[i][t]=min(f[i][t],v);
f[t][i]=min(f[t][i],v);
}
}
j=q[1];
k=q[1]-m;
t=2147483647;
for(i=0;i<=m;i++)
{
for(v=1;v<=n;v++)
{
r[v]=v;
}
t=min(dijkstra(k+i,j+i),t);
}

printf("%d",t);
return 0;
}```

Followed by: