团体程序设计天梯赛-练习集 - L3-011 直捣黄龙（30 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=250;
unordered_map<string,int>id;
unordered_map<int,string>name;
intn,m;
intvis[maxn], path[maxn], pre[maxn], cst[maxn], num[maxn], cost[maxn], dis[maxn];
intg[maxn][maxn];
voiddijkstra(ints)
{
dis[s]=0, path[s]=1;
while(1)
    {
intmi=INF; s=-1;
for(inti=1;i<=n;i++)
if(!vis[i] &&mi>dis[i]) mi=dis[i], s=i;
if(s==-1) return;
vis[s]=1;
for(inti=1;i<=n;i++)
        {
if(!vis[i] &&mi+g[s][i]<dis[i])
            {
dis[i]=mi+g[s][i];
pre[i]=s;
num[i]=num[s]+1;
path[i]=path[s];
cst[i]=cst[s]+cost[i];
            }
elseif(!vis[i] &&mi+g[s][i]==dis[i])
            {
path[i]+=path[s];
if(num[s]+1>num[i])
                {
pre[i]=s;
num[i]=num[s]+1;
cst[i]=cst[s]+cost[i];
                }
elseif(num[s]+1==num[i])
                {
if(cst[i]<cst[s]+cost[i])
                    {
pre[i]=s;
cst[i]=cst[s]+cost[i];
                    }
                }
            }
//            else if(!vis[i] && mi+g[s][i]==dis[i] && num[s]+1==num[i]) // 不能并列，需要放到第二条里面//            {//                path[i]+=path[s];//                if(cst[i]<cst[s]+cost[i])//                {//                    pre[i]=s;//                    cst[i]=cst[s]+cost[i];//                }//            }        }
    }
}
intmain()
{
mem(pre,-1), mem(g,INF), mem(dis,INF);
intth=0,w,u,v;
strings,d,ts,us,vs;
scanf("%d%d",&n,&m);
cin>>s>>d;
id[s]=++th, name[th]=s;
for(inti=1;i<n;i++)
    {
cin>>ts>>w;
id[ts]=++th, name[th]=ts;
cost[th]=w;
    }
for(inti=0;i<m;i++)
    {
cin>>us>>vs>>w;
g[id[us]][id[vs]]=g[id[vs]][id[us]]=w;
    }
dijkstra(id[s]);
vector<int>vec;
inth=id[d];
while(h!=-1)
    {
vec.push_back(h);
h=pre[h];
    }
for(inti=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]]);
return0;
}