uva11374 dij单源最短路+枚举

  1 //uva11374 dij单源最短路+枚举
  2 #include<iostream>
  3 #include<string.h>
  4 #include<stdio.h>
  5 #include<stdlib.h>
  6 #include<cmath>
  7 #include<algorithm>
  8 #include<queue>
  9 #include<stack>
 10 #include<set>
 11 #include<map>
 12 #define maxn 510
 13 #define INF 9999999
 14 using namespace std;
 15 
 16 struct Edge
 17 {
 18     int u,v,dis;
 19 };
 20 struct Node
 21 {
 22     int d,u;
 23     bool operator<(const Node &x)const{
 24         return d>x.d;
 25     }
 26 };
 27 struct Dijkstra
 28 {
 29     int n,m;
 30     vector<Edge>edge;
 31     vector<int>G[maxn];
 32     bool vis[maxn];
 33     int d[maxn],p[maxn];
 34 
 35     void init(int n)
 36     {
 37         this->n=n;
 38         edge.clear();
 39         for(int i=0;i<=n;i++) G[i].clear();
 40     }
 41 
 42     void add(int u,int v,int c){
 43         edge.push_back((Edge){u,v,c});
 44         m=edge.size();
 45         G[u].push_back(m-1);
 46     }
 47 
 48     void dij(int s)
 49     {
 50         memset(vis,0,sizeof(vis));
 51         for(int i=0;i<=n;i++) d[i]=INF;
 52         d[s]=0;
 53         priority_queue<Node>Q;
 54         Q.push((Node){0,s});
 55         while(!Q.empty()){
 56             Node x=Q.top();Q.pop();
 57             int u=x.u;
 58             if (vis[u]) continue;
 59             vis[u]=true;
 60             for(int i=0;i<G[u].size();i++)
 61             {
 62                 Edge &e=edge[G[u][i]];
 63                 if (d[e.v]>d[u]+e.dis){
 64                     d[e.v]=d[u]+e.dis;
 65                     p[e.v]=G[u][i];
 66                     Q.push((Node){d[e.v],e.v});
 67                 }
 68             }
 69         }
 70     }
 71 }Dij1,Dij2;
 72 
 73 int nextint(){int x;scanf("%d",&x);return x;}
 74 
 75 int  n,st,ed,m1,m2;
 76 
 77 void read()
 78 {
 79     m1=nextint();
 80     for(int i=0;i<m1;i++)
 81     {
 82         int u,v,c;
 83         u=nextint();v=nextint();c=nextint();
 84         Dij1.add(u,v,c);Dij2.add(u,v,c);
 85         Dij1.add(v,u,c);Dij2.add(v,u,c);
 86     }
 87     Dij1.dij(st);Dij2.dij(ed);
 88 }
 89 void solve()
 90 {
 91     int mind=Dij1.d[ed];
 92     bool ch=false;
 93     Edge e;
 94 
 95     int m2=nextint();
 96     for(int i=0;i<m2;i++)
 97     {
 98         int u,v,c;
 99         u=nextint();v=nextint();c=nextint();
100         if (Dij1.d[u]+c+Dij2.d[v]<mind){
101             mind=Dij1.d[u]+c+Dij2.d[v];
102             e=(Edge{u,v,c});
103             ch=true;
104         }
105         if (Dij1.d[v]+c+Dij2.d[u]<mind){
106             mind=Dij1.d[v]+c+Dij2.d[u];
107             e=(Edge{v,u,c});
108             ch=true;
109         }
110     }
111     vector<int>path,ans;
112     path.clear();ans.clear();
113     int u,v;
114     if (ch)
115     {
116         u=e.u;
117         while(u!=st)
118         {
119             path.push_back(u);
120             u=Dij1.edge[Dij1.p[u]].u;
121         }
122         path.push_back(st);
123         for(int i=path.size()-1;i>=0;i--) ans.push_back(path[i]);
124 
125         v=e.v;
126         while(v!=ed)
127         {
128             ans.push_back(v);
129             v=Dij2.edge[Dij2.p[v]].u;
130         }
131         ans.push_back(ed);
132     }
133     else{
134         v=st;
135         while(v!=ed)
136         {
137             ans.push_back(v);
138             v=Dij2.edge[Dij2.p[v]].u;
139         }
140         ans.push_back(ed);
141     }
142 
143     for(int i=0;i<ans.size();i++)
144     {
145         if (i>0) printf(" ");
146         printf("%d",ans[i]);
147     }
148     printf("\n");
149     if (ch) printf("%d\n",e.u);else printf("Ticket Not Used\n");
150     printf("%d\n",mind);
151 
152     return ;
153 }
154 int main()
155 {
156     int cas=0;
157     while(cin>>n>>st>>ed && n>0)
158     {
159         cas++;
160         if (cas>1) printf("\n");
161         Dij1.init(n);Dij2.init(n);
162         read();
163         solve();
164     }
165 }