本文共 1955 字，大约阅读时间需要 6 分钟。

题目链接：

题目大意：略。

解题思路：AC1 代码 和 AC2 代码（推荐）的区别在于：代码1的初始化为 mem(dis,0) 在进入 for(int i=1;i<n-1;i++) 之前已经初始化好 第一个 s 的更新；而代码2的初始化为 mem(dis,INF) 在进入 while(1) 之前没有进行第一个 s 的更新，而是把这个操作放在 while(1) 里面，这样就可以把第一个 s 赋值给 pre[] 数组。即：代码2中第一个 s 的更新工作其实就是代码1进入 for(int i=1;i<n-1;i++) 之前的更新工作，只是为了更新第一个 pre[]=s 而已。

AC1 代码（常规版）

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=510;int n,m,s,d;int mp[maxn][maxn], cost[maxn][maxn];int vis[maxn], dis[maxn], cst[maxn], pre[maxn];vector
     
       vec;void init(){    mem(vis,0), mem(cst,0), mem(dis,0), mem(pre,-1);    mem(mp,INF), mem(cost,INF);}int dijkstra(int s){    for(int i=0;i
      
       cst[v]+cost[v][j])                cst[j]=cst[v]+cost[v][j], pre[j]=v;        }    }}int main(){    init();    int a,b,u,v;    scanf("%d%d%d%d",&n,&m,&s,&d);    for(int i=0;i
       
        =0;i--) printf("%d ",vec[i]);        printf("%d %d\n",dis[d],cst[d]);    }    else puts("-1");    return 0;}
       
      
     
    
   

AC2 代码（简化版）

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=510;int n,m,s,d;int mp[maxn][maxn], cost[maxn][maxn];int vis[maxn], dis[maxn], cst[maxn], pre[maxn];vector
     
       vec;void init(){    mem(vis,0), mem(cst,0), mem(dis,INF), mem(pre,-1);    mem(mp,INF), mem(cost,INF);}int dijkstra(int s){    dis[s]=0;    while(1)    {        int mi=INF,s=-1;        for(int j=0;j
      
       cst[s]+cost[s][j])                cst[j]=cst[s]+cost[s][j], pre[j]=s;        }    }}int main(){    init();    int a,b,u,v;    scanf("%d%d%d%d",&n,&m,&s,&d);    for(int i=0;i
       
        =0;i--) printf("%d ",vec[i]);        printf("%d %d\n",dis[d],cst[d]);    }    else puts("-1");    return 0;}
       
      
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/82054361 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！