Uva11374 Dijkstra

机场快线是市民从市内去机场的首选交通工具。机场快线分为经济线和商业线两种，线路、速度和价格都不同，你有一张商业线车票，可以坐一站商业线，而其他时候，只能乘坐经济线。假设换乘时间忽略不计，你的任务是找一条去机场最快的路线。

这样我们先从起点开始做一次dijkstra 然后在从终点开始做一次dijkstra， 然后枚举每个商业边。

#include <iostream>

#include <algorithm>

#include <string.h>

#include <cstdio>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

const int INF =;

const int maxn = +;

struct Edge{

  int from,to,dist;

};

struct HeapNoda{

   int d,u;

   bool operator <(const HeapNoda &rhs)const{

     return d>rhs.d;

   }

};

struct Dijkstra{

      int n,m;

      vector<Edge> edges;

      vector<int>G[maxn];

      bool done[maxn];

      int d[maxn];

      int p[maxn];

      void inti(int n){

        this->n=n;

        for(int i=; 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-);

      }

      void dijkstra(int s){

          priority_queue<HeapNoda> Q;

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

          d[s]=;

          memset(done,,sizeof(done));

          Q.push((HeapNoda){,s});

          while(!Q.empty()){

              HeapNoda 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] = G[u][i];

                      Q.push((HeapNoda){d[e.to],e.to});

                 }

              }

          }

      }

      void GetshortPaths(int s, int *dist, vector<int> *paths){

          dijkstra(s);

          for(int i=; 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()

{

     int N,S,E,M,kase=,X,Y,Z,K;

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

            S-- ; E--;

          scanf("%d",&M);

          solver.inti(N);

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

               scanf("%d%d%d",&X,&Y,&Z);X--; Y--;

               solver.AddEdge(X,Y,Z);

               solver.AddEdge(Y,X,Z);

          }

          solver.GetshortPaths(S,d1,paths1);

          solver.GetshortPaths(E,d2,paths2);

          int ans = d1[E];

          vector<int>path = paths1[E];

          int midpoint=-;

          scanf("%d",&K);

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

               scanf("%d%d%d",&X,&Y,&Z); X--; Y--;

               for(int j=; j<; j++){

                 if(d1[X]+d2[Y]+Z<ans){

                    ans=d1[X]+d2[Y]+Z;

                    path=paths1[X];

                    midpoint=X;

                    for(int a = paths2[Y].size()-; a>=; a--){

                        path.push_back( paths2[Y][a] );

                    }

                 }

                 swap(X,Y);

               }

          }

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

          kase=;

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

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

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

          if(midpoint==-) printf("Ticket Not Used\n");

          else printf("%d\n",midpoint+);

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

     }

    return ;

}