题意：
众所周知，TT 有一只魔法猫。
今天他在 B 站上开启了一次旅行直播，记录他与魔法猫在喵星旅游时的奇遇。 TT 从家里出发，准备乘坐猫猫快线前往喵星机场。猫猫快线分为经济线和商业线两种，它们的速度与价钱都不同。当然啦，商业线要比经济线贵，TT 平常只能坐经济线，但是今天 TT 的魔法猫变出了一张商业线车票，可以坐一站商业线。假设 TT 换乘的时间忽略不计，请你帮 TT 找到一条去喵星机场最快的线路，不然就要误机了！
输入
输入包含多组数据。
每组数据第一行为 3 个整数 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即猫猫快线中的车站总数，起点和终点（即喵星机场所在站）编号。
下一行包含一个整数 M (1 ≤ M ≤ 1000)，即经济线的路段条数。
接下来有 M 行，每行 3 个整数 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐经济线在车站 X 和车站 Y 之间往返，其中单程需要 Z 分钟。
下一行为商业线的路段条数 K (1 ≤ K ≤ 1000)。
接下来 K 行是商业线路段的描述，格式同经济线。
所有路段都是双向的，但有可能必须使用商业车票才能到达机场。保证最优解唯一。
输出
对于每组数据，输出3行。第一行按访问顺序给出 TT 经过的各个车站（包括起点和终点），第二行是 TT 换乘商业线的车站编号（如果没有使用商业线车票，输出"Ticket Not Used"，不含引号），第三行是 TT 前往喵星机场花费的总时间。
本题不忽略多余的空格和制表符，且每一组答案间要输出一个换行
输入样例
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
输出样例
1 2 4
25
My Solution：
本题商业线的引入使得问题变得复杂化，如果没有商业线，则问题变成了简单的图问题中的最短路问题。
我们发现加入商业线以后有两种做法，最短路中包含一条商业线或者不包含商业线。
对于不包含商业线的情况，我们可以求一个最短路。
对于包含商业线的情况，因为只走一条商业线，我们可以枚举每一条商业线的情况，然后取最小。
接下来，对于走(一条)商业线的问题怎么求短路呢？
分别从起点和终点跑一次最短路，然后取两次的最小值
min (dis1[u]+dis2[v]+w , dis1[v]+dis2[u]+w )
最后合并以上 以上情况，取最小即可！
1 #include<iostream>
2 #include<string.h>
3 #include<algorithm>
4 using namespace std;
5 const int maxn=1000010;
6 int n,m,k,s,e,tot,ans=10000000,sum;
7 int head[maxn],dis1[maxn],dis2[maxn];
8 int pre1[maxn],pre2[maxn];
9 int p[maxn],a[maxn];
10 bool flag[maxn];
11 int ans_u,ans_v,ans_w;
12 struct node
13 {
14 int v;
15 int w;
16 int next;
17 }e1[maxn];
18 void add_edge(int u,int v,int w)
19 {
20 e1[++tot].v=v;
21 e1[tot].w=w;
22 e1[tot].next=head[u];
23 head[u]=tot;
24 }
25
26 void dijkstra(int u,int *dis,int *pre)
27 {
28 memset(flag,0,sizeof(flag));
29 for(int i=1;i<=n;i++)
30 dis[i]=maxn;
31 dis[u]=0;
32 for(int i=1;i<=n;i++)
33 {
34 int k=0,minn=maxn;
35 for(int j=1;j<=n;j++)
36 if(!flag[j]&&dis[j]<minn)
37 {
38 minn=dis[j];
39 k=j;
40 }
41 flag[k]=1;
42 for(int j=head[k];j;j=e1[j].next)
43 if(!flag[e1[j].v]&&dis[e1[j].v]>dis[k]+e1[j].w) //松弛
44 {
45 dis[e1[j].v]=dis[k]+e1[j].w;
46 pre[e1[j].v]=k;
47 }
48 }
49 }
50 int main()
51 {
52 int x,y,z,u,v,w;
53 cin>>n>>s>>e;
54 while(1)
55 {
56 memset(flag,0,sizeof(flag));
57 memset(pre1,0,sizeof(pre1));
58 memset(pre2,0,sizeof(pre2));
59 memset(head,0,sizeof(head));
60 memset(a,0,sizeof(a));
61 tot=0;
62 cin>>m;
63 ans_u=0;sum=0;
64 for(int i=1;i<=m;i++)
65 {
66 cin>>x>>y>>z;
67 add_edge(x,y,z);
68 add_edge(y,x,z);
69 }
70
71 dijkstra(s,dis1,pre1) ;
72 dijkstra(e,dis2,pre2) ;
73
74 cin>>k;
75 int ans=dis1[e];
76 for(int i=1;i<=k;i++)
77 {
78 cin>>u>>v>>w;
79 if(dis1[u]+dis2[v]+w<ans)
80 {
81 ans=dis1[u]+dis2[v]+w;
82 ans_u=u;
83 ans_v=v;
84 }
85 if(dis2[u]+dis1[v]+w<ans)//再次更新
86 {
87 ans=dis2[u]+dis1[v]+w;
88 ans_u=v;
89 ans_v=u;
90 }
91 }
92 int tmp;
93 if(ans_u==0)//不需要商务线
94 {
95 tmp=e;
96 while(tmp)
97 {
98 a[++sum]=tmp;
99 if(tmp==s) break;
100 tmp=pre1[tmp];
101 }
102 for(int i=sum;i>=2;i--) cout<<a[i]<<" ";
103 cout<<a[1]<<endl;
104 cout<<"Ticket Not Used"<<endl<<ans<<endl;
105 }
106 else//需要商务线
107 {
108 tmp=ans_v;
109 while(tmp)
110 {
111 a[++sum]=tmp;
112 if(tmp==e) break;
113 tmp=pre2[tmp];
114 }
115 for(int i=1;i<=sum/2;i++)
116 swap(a[i],a[sum-i+1]);
117 tmp=ans_u;
118 while(tmp)
119 {
120 a[++sum]=tmp;
121 if(tmp==s) break;
122 tmp=pre1[tmp];
123 }
124 for(int i=sum;i>=2;i--) cout<<a[i]<<" ";
125 cout<<a[1]<<endl;
126 cout<<ans_u<<endl<<ans<<endl;
127 }
128
129 if(cin>>n>>s>>e)
130 cout<<endl; //每个输出换行
131 else
132 break;
133 }
134 return 0;
135 }