L2-001. 紧急救援

L2-001. 紧急救援

最短路+一些细节操作

#include<bits/stdc++.h>

using namespace std;
int N,M,S,D;
const int maxn = 500+100;
int num[maxn];
int away[maxn][maxn];
int dis[maxn];
bool vis[maxn];
const int INF = 1e8;
int F[maxn];
int path[maxn];
int All[maxn];
int main(void)
{
    cin>>N>>M>>S>>D;
    for(int i = 0; i < N; ++i)
        F[i] = S;
    for(int i  = 0; i < N; ++i)
        scanf("%d",&num[i]);
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++ j)
        {
            away[i][j] = INF;
        }
    }
    for(int i = 0; i < M; ++i)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        away[a][b] = away[b][a] = min(c,away[a][b]);
    }
    for(int i = 0; i < N; ++i)
        dis[i] = (i == S?0:INF);
    vector<int> vec;
    int Allnum = 0;
    path[S] = 1;
    while(1)
    {
        int M1 = INF,M2 = INF,index;
        for(int i = 0; i < N; ++i)
        {
// if(!vis[i]&&(dis[i] < M1||(dis[i] == M1&&num[i] > M2)))
            if(!vis[i]&&dis[i] < M1)
            {
                index = i;
                M1 = dis[i];
                M2 = num[i];
            }
        }
        vis[index] = 1;
        if(F[index] != -1)
            All[index] = All[F[index]] + num[index];
        else
            All[index] = num[index];
        if(index == D)
            break;
        for(int i = 0; i < N ; ++i)
        {
            if(!vis[i] && dis[i] >= dis[index] + away[i][index])
            {
                if(dis[i] > dis[index] + away[i][index])
                    path[i] = path[index],F[i] = index;
                else
                {
                    path[i] += path[index];
                    F[i] = All[F[i]] > All[index] ? F[i]:index;
                }
                dis[i] = dis[index] + away[i][index];
            }
        }
    }
    int T = D;
    vec.push_back(T);
    Allnum += num[T];
    while(T != S)
    {
        T = F[T];
        vec.push_back(T);
        Allnum += num[T];
    }
    cout<<path[D]<<" ";
    cout<<Allnum<<endl;
    for(int i = vec.size()-1; i >= 0 ; --i)
    {
        cout<<vec[i];
        if(i)
            putchar(' ');
    }



    return 0;
}