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

题目链接：

题目大意：略。

解题思路：注意判断条件时的次序严格性的问题。

AC 代码

#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=250;unordered_map
     
       id;unordered_map
      
        name;int n,m;int vis[maxn], path[maxn], pre[maxn], cst[maxn], num[maxn], cost[maxn], dis[maxn];int g[maxn][maxn];void dijkstra(int s){    dis[s]=0, path[s]=1;    while(1)    {        int mi=INF; s=-1;        for(int i=1;i<=n;i++)            if(!vis[i] && mi>dis[i]) mi=dis[i], s=i;        if(s==-1) return;        vis[s]=1;        for(int i=1;i<=n;i++)        {            if(!vis[i] && mi+g[s][i]
       
        num[i])                {                    pre[i]=s;                    num[i]=num[s]+1;                    cst[i]=cst[s]+cost[i];                }                else if(num[s]+1==num[i])                {                    if(cst[i]
        
         >s>>d; id[s]=++th, name[th]=s; for(int i=1;i
         
          >ts>>w; id[ts]=++th, name[th]=ts; cost[th]=w; } for(int i=0;i
          
           >us>>vs>>w; g[id[us]][id[vs]]=g[id[vs]][id[us]]=w; } dijkstra(id[s]); vector
           
             vec; int h=id[d]; while(h!=-1) { vec.push_back(h); h=pre[h]; } for(int i=vec.size()-1;i>=0;i--) printf("%s%s",name[vec[i]].c_str(),i==0?"\n":"->"); printf("%d %d %d\n",path[id[d]],dis[id[d]],cst[id[d]]); return 0;}
           
          
         
        
       
      
     
    
   

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