训练指南 UVA - 11374（最短路Dijkstra + 记录路径 + 模板）

Diposting di | Edited on

Airport Express

UVA - 11374

题意

机场快线有经济线和商业线,现在分别给出经济线和商业线的的路线,现在只能坐一站商业线,其他坐经济线,问从起点到终点的最短用时是多少,还有路线是怎样的;

题解

预处理出起点到所有站的最短距离和终点到所有站的最短距离,枚举要坐的那趟商业线,然后里面最小的就是答案了;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=550;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,u;
    bool operator <(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m;              //点数和边数  点编号0~N-1
    vector<Edge>edges;
    vector<int>G[maxn];
    bool done[maxn];
    int d[maxn];
    int p[maxn];

    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();
        edges.clear();
    }
    void AddEdge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }
    void dijkstra(int s){
        priority_queue<HeapNode>Q;
        for(int i=0;i<n;i++)d[i]=inf;
        d[s]=0;
        memset(done,0,sizeof(done));
        Q.push((HeapNode){0,s});
        while(!Q.empty()){
            HeapNode x=Q.top();Q.pop();
            int u=x.u;
            if(done[u])continue;
            done[u]=true;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to]=d[u]+e.dist;
                    p[e.to]=G[u][i];
                    Q.push((HeapNode){d[e.to],e.to});
                }
            }
        }
    }

    void GetShortestPaths(int s,int* dist,vector<int>* paths){//paths是二维链表
        dijkstra(s);
        for(int i=0;i<n;i++){
            dist[i]=d[i];
            paths[i].clear();
            int t=i;
            paths[i].push_back(t);
            while(t!=s){
                paths[i].push_back(edges[p[t]].from);
                t=edges[p[t]].from;
            }
            reverse(paths[i].begin(),paths[i].end());
        }
    }
};

Dijkstra solver;
int d1[maxn],d2[maxn];
vector<int>paths1[maxn],paths2[maxn];
int main()
{
   // std::ios::sync_with_stdio(false);
   // std::cin.tie(0);
   // std::cout.tie(0);
    int kase=0,N,S,E,M,K,X,Y,Z;
    while(scanf("%d%d%d%d", &N, &S, &E, &M) == 4) {
        solver.init(N);
        S--;E--;
        for(int i=0;i<M;i++){
            scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
            solver.AddEdge(X,Y,Z);
            solver.AddEdge(Y,X,Z);
        }
        solver.GetShortestPaths(S,d1,paths1);
        solver.GetShortestPaths(E,d2,paths2);
        int ans=d1[E];
        vector<int>path=paths1[E];
        int midpoint=-1;
        scanf("%d", &K);
        for(int i=0;i<K;i++){
            scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
            for(int j=0;j<2;j++){
                if(d1[X]+d2[Y]+Z<ans){
                    ans=d1[X]+d2[Y]+Z;
                    path=paths1[X];
                    for(int p=paths2[Y].size()-1;p>=0;p--)
                        path.push_back(paths2[Y][p]);
                    midpoint=X;
                }
                swap(X,Y);
            }
        }
        
        if(kase != 0) printf("\n");
        kase++;
        for(int i = 0; i < path.size()-1; i++) printf("%d ", path[i]+1);
        printf("%d\n", E+1);
        if(midpoint == -1) printf("Ticket Not Used\n"); else printf("%d\n", midpoint+1);
        printf("%d\n", ans);
    }
    return 0;
}