> /*
> 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;
> 
> }

• Re:求助啊啊啊，用dijkstra做WA到底，找了能找的测试数据均通过了啊，附代码（有注释啊啊） (16) yaoguang2034 2020-04-06 12:08:12