数据结构与算法题目集（中文） - 7-35 城市间紧急救援（25 分）

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=510;
int n,m,s,d;
int vis[maxn], pathCnt[maxn], tms[maxn], pre[maxn], teams[maxn], dis[maxn];
int g[maxn][maxn];
vector<int> vec;
void init()
{
    mem(pathCnt,0); mem(vis,0); mem(pre,-1);
    vec.clear();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            g[i][j]=INF;
    }
}
void dijkstra()
{
    for(int i=0;i<n;i++) dis[i]=g[s][i];
    pathCnt[s]=1;
    vis[s]=1;
    dis[s]=0;
    while(s!=d)
    {
        for(int i=0;i<n;i++)
        {
            if(!vis[i])
            {
                if(dis[s]+g[s][i]<dis[i])
                {
                    dis[i]=dis[s]+g[s][i];
                    pre[i]=s;
                    pathCnt[i]=pathCnt[s];
                    teams[i]=teams[s]+tms[i];
                }
                else if(dis[s]+g[s][i]==dis[i])
                {
                    pathCnt[i]+=pathCnt[s];
                    if(teams[s]+tms[i]>teams[i])
                    {
                        teams[i]=teams[s]+tms[i];
                        pre[i]=s;
                    }
                }
            }
        }
        int mi=INF;
        for(int i=0;i<n;i++)
        {
            if(!vis[i] && dis[i]<mi)
            {
                mi=dis[i];
                s=i;
            }
        }
        vis[s]=1;
    }
}
int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&s,&d))
    {
        init();
        for(int i=0;i<n;i++)
        {
            scanf("%d",&tms[i]);
            teams[i]=tms[i];
        }
        int u,v,w;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            g[u][v]=g[v][u]=w;
        }
        dijkstra();
        printf("%d %d\n",pathCnt[d],teams[d]);
        int h=d;
        while(h!=-1)
        {
            vec.push_back(h);
            h=pre[h];
        }
        int len=vec.size();
        printf("%d",vec[len-1]);
        for(int i=len-2;i>=0;i--) printf(" %d",vec[i]);
        puts("");
    }
    return 0;
}