UVA 11374 Airport Express （最短路）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目只有一条路径会发生改变。

常见的思路，预处理出S和T的两个单源最短路，然后枚举商业线，商业线两端一定是选择到s和t的最短路。

路径输出可以在求最短路的同时保存pa数组得到一棵最短路树，也可以用dist数组检查。

#include<bits/stdc++.h>

using namespace std;

const int maxn = , maxm = ;

int head[maxn], to[maxm], nxt[maxm],wei[maxm],ecnt;

void addEdge(int u,int v,int w)

{

    to[ecnt] = v;

    nxt[ecnt] = head[u];

    wei[ecnt] = w;

    head[u] = ecnt++;

}

typedef pair<int,int> Node;

#define fi first

#define se second

const int INF = 0x3f3f3f3f;

int d1[maxn],d2[maxn];

void dijkstra(int s,int t,int (&d)[maxn])

{

    priority_queue<Node,vector<Node>,greater<Node> > q;

    memset(d,0x3f,sizeof(d));

    d[s] = ; q.push(Node(,s));

    while(q.size()){

        Node x = q.top(); q.pop();

        int u = x.se;

        if(x.fi != d[u]) continue;

        for(int i = head[u]; ~i; i = nxt[i]){

            int v = to[i];

            if(d[v] > d[u]+wei[i]){

                d[v] = d[u]+wei[i];

                q.push(Node(d[v],v));

            }

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    int N,S,E;

    bool first = true;

    while(~scanf("%d%d%d",&N,&S,&E)){

        if(!first) putchar('\n');

        first = false;

        int M; scanf("%d",&M);

        memset(head,-,sizeof(head));

        ecnt = ;

        while(M--){

            int u,v,w; scanf("%d%d%d",&u,&v,&w);

            addEdge(--u,--v,w); addEdge(v,u,w);

        }

        dijkstra(--S,--E,d1);

        dijkstra(E,S,d2);

        int pick = -, p2, ans = d1[E];

        int K; scanf("%d",&K);

        for(int i = ; i < K; i++){

            int u,v,w; scanf("%d%d%d",&u,&v,&w);

            if(d1[--u] + w  < ans - d2[--v]){

                ans = d1[u] + w + d2[v];

                pick = u; p2 = v;

            }else if( d2[u] + w  < ans - d1[v]){

                ans = d2[u] + w + d1[v];

                pick = v; p2 = u;

            }

        }

        int u;

        if(~pick){

            stack<int> stk;

            u = pick;

            stk.push(u);

            while(u != S){

                for(int i = head[u]; ~i; i = nxt[i]){

                    if(d1[u] - wei[i] == d1[to[i]] ){

                        u = to[i]; stk.push(u); break;

                    }

                }

            }

            while(stk.size()){

                printf("%d ",stk.top()+); stk.pop();

            }

            u = p2;

        }else {

            u = S;

        }

        while(u != E){

            printf("%d ",u+);

            for(int i = head[u]; ~i; i = nxt[i]){

                if(d2[u] - wei[i] == d2[to[i]] ){

                    u = to[i];  break;

                }

            }

        }

        printf("%d\n",E+);

        if(~pick) printf("%d\n",pick+);

        else puts("Ticket Not Used");

        printf("%d\n",ans);

    }

    return ;

}