/*
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到底，找了能找的测试数据均通过了啊，附代码（有注释啊啊） (1994) yaoguang2034 2020-04-06 12:07:45
  • Re:求助啊啊啊，用dijkstra做WA到底，找了能找的测试数据均通过了啊，附代码（有注释啊啊） (16) yaoguang2034 2020-04-06 12:08:12