PAT (Advanced Level) Practice - 1111 Online Map（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=520;
intn,m;
intvis[maxn], dis[maxn], fst[maxn], pre1[maxn], pre2[maxn], num[maxn];
intg[maxn][maxn], fast[maxn][maxn];
vector<int>path1,path2;
intdijkstra1(ints)
{
dis[s]=0, fst[s]=0;
while(1)
    {
intmi=INF; s=-1;
for(inti=0;i<n;i++)
if(!vis[i] &&dis[i]<mi) mi=dis[i], s=i;
if(s==-1) return0;
vis[s]=1;
for(inti=0;i<n;i++)
        {
if(!vis[i] &&mi+g[s][i]<dis[i])
            {
dis[i]=mi+g[s][i];
fst[i]=fst[s]+fast[s][i];
pre1[i]=s;
            }
elseif(!vis[i] &&mi+g[s][i]==dis[i] &&fst[s]+fast[s][i]<fst[i])
            {
fst[i]=fst[s]+fast[s][i];
pre1[i]=s;
            }
        }
    }
}
intdijkstra2(ints)
{
fst[s]=0;
while(1)
    {
intmi=INF; s=-1;
for(inti=0;i<n;i++)
if(!vis[i] &&fst[i]<mi) mi=fst[i], s=i;
if(s==-1) return0;
vis[s]=1;
for(inti=0;i<n;i++)
        {
if(!vis[i] &&mi+fast[s][i]<fst[i])
            {
fst[i]=mi+fast[s][i];
num[i]=num[s]+1;
pre2[i]=s;
            }
elseif(!vis[i] &&mi+fast[s][i]==fst[i] &&num[s]+1<num[i])
            {
num[i]=num[s]+1;
pre2[i]=s;
            }
        }
    }
}
intmain()
{
mem(g,INF), mem(fast,INF), mem(dis,INF), mem(pre1,-1), mem(pre2,-1), mem(num,0);
intu,v,t,l,f;
scanf("%d%d",&n,&m);
for(inti=0;i<m;i++)
    {
scanf("%d%d%d%d%d",&u,&v,&f,&l,&t);
if(f) g[u][v]=l, fast[u][v]=t;
elseg[v][u]=g[u][v]=l, fast[v][u]=fast[u][v]=t;
    }
scanf("%d%d",&u,&v);
mem(vis,0), mem(fst,INF);
dijkstra1(u);
mem(vis,0), mem(fst,INF);
dijkstra2(u);
inth=v;
while(h!=-1)
    {
path1.push_back(h);
h=pre1[h];
    }
h=v;
while(h!=-1)
    {
path2.push_back(h);
h=pre2[h];
    }
if(path1==path2)
    {
printf("Distance = %d; Time = %d: ",dis[v],fst[v]);
for(inti=path1.size()-1;i>=0;i--)
printf("%d%s",path1[i],i==0?"\n":" -> ");
    }
else    {
printf("Distance = %d: ",dis[v]);
for(inti=path1.size()-1;i>=0;i--)
printf("%d%s",path1[i],i==0?"\n":" -> ");
printf("Time = %d: ",fst[v]);
for(inti=path2.size()-1;i>=0;i--)
printf("%d%s",path2[i],i==0?"\n":" -> ");
    }
return0;
}