UVa 11374 机场快线

https://vjudge.net/problem/UVA-11374

题意：

机场快线分为经济线和商业线两种，线路、速度和价格都不同。你有一张商业线车票，可以坐一站商业线，而其他时候只能乘坐经济线。你的任务是找一条去机场最快的线路。

思路：

因为商业线只能坐一站，所有可以枚举坐的是哪一站，用dijkstra算出起点到每个点的最短时间f(x)和终点到每个点的最短时间g(x)，则总时间为f(a)+T(a,b)+g(b)，其中T（a，b）为从a坐一站商业线到达b的时间。

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <queue>

 using namespace std;

 const int INF = ;

 const int maxn =  + ;

 struct Edge

 {

     int from, to, dist;

     Edge(int u, int v, int d) :from(u), to(v), dist(d){}

 };

 struct HeapNode

 {

     int d, u;

     HeapNode(int x, int y) :d(x), u(y){}

     bool operator < (const HeapNode& rhs) const{

         return d > rhs.d;

     }

 };

 struct Dijkstra

 {

     int n, m;                  //点数和边数

     vector<Edge> edges;        //边列表

     vector<int> G[maxn];       //每个结点出发的边编号（从0开始编号）

     bool done[maxn];           //是否已永久标号

     int d[maxn];               //s到各个点的距离

     int p[maxn];               //最短路中的上一条边

     void init(int n)

     {

         this->n = n;

         for (int i = ; i < n; i++)    G[i].clear();

         edges.clear();

     }

     void AddEdges(int from, int to, int dist)

     {

         edges.push_back(Edge(from,to,dist));

         m = edges.size();

         G[from].push_back((m - ));

     }

     void dijkstra(int s)

     {

         priority_queue<HeapNode> Q;

         for (int i = ; i < n; i++)    d[i] = INF;

         d[s] = ;

         memset(done, , sizeof(done));

         Q.push(HeapNode(,s));

         while (!Q.empty())

         {

             HeapNode x = Q.top(); Q.pop();

             int u = x.u;

             if (done[u]) continue;

             done[u] = true;

             for (int i = ; 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] = e.from;

                     Q.push(HeapNode(d[e.to],e.to));

                 }

             }

         }

     }

     void getpath(int s, int e, vector<int>& path)

     {

         int pos = e;

         while (true)

         {

             path.push_back(pos);

             if (pos == s)

                 break;

             pos = p[pos];

         }

     }

 }t[];

 int N, S, E;

 vector<int> path;

 int main()

 {

     //freopen("D:\\input.txt", "r", stdin);

     int time, kase = ;

     while (scanf("%d%d%d", &N, &S, &E) != EOF)

     {

         S--; E--;

         if (kase != )   printf("\n");

         kase++;

         t[].init(N);

         t[].init(N);

         path.clear();

         int M, K;

         int u, v, d;

         scanf("%d", &M);

         while (M--)

         {

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

             u--; v--;

             t[].AddEdges(u, v, d);

             t[].AddEdges(u, v, d);

             t[].AddEdges(v, u, d);

             t[].AddEdges(v, u, d);

         }

         t[].dijkstra(S);

         t[].dijkstra(E);

         int ks = -, ke = -;

         time = t[].d[E];

         scanf("%d", &K);

         while (K--)

         {

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

             u--;v--;

             if (d + t[].d[u] + t[].d[v] < time){

                 time = d + t[].d[u] + t[].d[v];

                 ks = u; ke = v;

             }

             if (d + t[].d[v] + t[].d[u] < time){

                 time = d + t[].d[v] + t[].d[u];

                 ks = v; ke = u;

             }

         }

         if (ks == -)

         {

             t[].getpath(S, E, path);

             reverse(path.begin(), path.end());

             for (int i = ; i < path.size() - ; i++)

                 printf("%d ", path[i]+);

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

             printf("Ticket Not Used\n");

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

         }

         else

         {

             t[].getpath(S, ks, path);

             reverse(path.begin(), path.end());

             t[].getpath(E, ke, path);

             for (int i = ; i < path.size() - ; i++)

                 printf("%d ", path[i]+ );

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

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

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

         }

     }

     return ;

 }