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

## 求助啊啊啊，用dijkstra做WA到底，找了能找的测试数据均通过了啊，附代码（有注释啊啊）

Posted by jus_one at 2015-03-04 21:55:59 on Problem 1062
```/*
1。与酋长等级差超过m直接排除
2.分别以j（2...n）为源点，1为终点执行dijkstra（执行前先排除等级不在范围的点）
3.取得所有结果的最小值
*/
#include<cstdio>
#include<cstring>
#define INF 0x03f3f3f3f
const int N=101;
int dist[N],G[N][N],level[N],money[N];
bool vis[N];
int left,right;
bool under_limit(int l)
{
return  (l>=left&&l<=right);
}
int  dijkstra(int s,int n)
{
int i,j,min;
vis[s]=true;
for(i=1;i<=n;++i){
dist[i]=INF;
}
dist[s]=0;
int pre=s;
for(i=1;i<n;++i){
min=INF;
for(j=1;j<=n;++j)//取得最优点pre
if(!vis[j]&&dist[j]<min)
min=dist[j],pre=j;
for(j=1;j<=n;++j)//更新dist
if(vis[j]==0&&(dist[pre]+G[pre][j]<dist[j]))
dist[j]=dist[pre]+G[pre][j];
vis[pre]=true;
}
return dist[1];
}
int min(int a,int b){return a<b?a:b;}
int main()
{
int i,j,n,m,p,l,x,t,v;
scanf("%d %d",&m,&n);
for(i=0;i<N;++i)
for(j=0;j<N;++j)G[i][j]=INF;
for(i=1;i<=n;++i){
scanf("%d %d %d",&p,&l,&x);
level[i]=l,money[i]=p;
for(j=0;j<x;++j)
{
scanf("%d %d",&t,&v);
G[t][i]=v;
}
}
int ans=INF;
for(i=1;i<=n;++i)
if(level[i]-level[1]<=m&&level[i]-level[1]>=-m){/*起点与终点等级相差不大于M*/
if(level[i]<level[1])/*计算得到以j为起点1为终点要求的等级范围*/
left=level[1]-m,right=level[i]+m;
else
left=level[i]-m,right=level[1]+m;
memset(vis,0,sizeof(vis));
for(j=1;j<=n;++j)
{
if(!under_limit(level[j]))/*把不在范围的点标记为已访问，表示不再访问*/
vis[j]=true;
}
ans=min(dijkstra(i,n)+money[i],ans);/**/
}
printf("%d\n",ans);
return 0;

}
```

Followed by: