题目大意：机场快线分为经济线和商业线两种，线路，速度和价钱都不同。你有一张商业线车票，可以坐一站商业线，而其他时候只能坐经济线
现在给你起点和终点，要求你找出一条最快的线路

解题思路：不得不说，这题还是有点恶心的
要进行两次的dijkstra，一次以起点为源点，得到的数组d1表示结点和起点最近距离
另一次以终点为源点，得到数组d2,表示结点和终点最近的距离

现在M张商业票,给出的地点为x,y,z
那么有两种选择方式，一种是从起点走到x，然后使用商业票，然后再从y走到终点，那么距离就为 d1[x] + z + d2[y]
另外一种方式就是从起点走到y，然后使用商业票，再从y走到终点，那么距离就为d1[y] + z + d2[x]
找出其中的最小值就可以了
接下来就是恶心的输出路径问题了

#include 
   
     #include 
    
      #include 
     
       using namespace std; #define N 510 #define M 1010 #define INF 0x3f3f3f3f struct Node{ int x, y; }node[M]; int dis[N][N], d1[N], d2[N], pre1[N], pre2[N]; bool vis[N]; int n, s, e, m, k; void init() { scanf(%d, &m); memset(dis, 0x3f, sizeof(dis)); int x, y, z; for (int i = 0; i < m; i++) { scanf(%d%d%d, &x, &y, &z); dis[x][y] = dis[y][x] = min(dis[x][y], z); } } void dijstra(int s, int *d, int *pre) { memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) d[i] = INF; d[s] = 0; for (int i = 1; i <= n - 1; i++) { int x, t = INF; for (int j = 1; j <= n; j++) { if (!vis[j] && d[j] < t) { t = d[j]; x = j; } } vis[x] = 1; for (int j = 1; j <= n; j++) if (d[j] > d[x] + dis[x][j]) { d[j] = d[x] + dis[x][j]; pre[j] = x; } } } void print_path(int pos, int flag) { int cnt = 1, ans[N]; if (pos == -1) { ans[0] = e; int t = e; while (pre1[t] != s) { ans[cnt++] = pre1[t]; t = pre1[t]; } printf(%d, s); for (int i = cnt - 1; i >= 0; i--) printf( %d, ans[i]); printf( ); return ; } int x, y; if (flag == 0) { x = node[pos].x; y = node[pos].y; } else { x = node[pos].y; y = node[pos].x; } if (x != s) { ans[0] = x; while (pre1[x] != s) { ans[cnt++] = pre1[x]; x = pre1[x]; } printf(%d, s); for (int i = cnt - 1; i >= 0; i--) printf( %d, ans[i]); } else { printf(%d, s); } if (y != e){ printf( %d, y); while (pre2[y] != e) { printf( %d, pre2[y]); y = pre2[y]; } printf( %d, e); } else { printf( %d, y); } printf( ); return ; } void solve() { dijstra(s, d1, pre1); dijstra(e, d2, pre2); scanf(%d, &k); int pos = -1, flag = 0, Min = d1[e]; int x, y, z; for (int i = 0; i < k; i++) { scanf(%d%d%d, &x, &y, &z); node[i].x = x; node[i].y = y; if (Min > d1[x] + z + d2[y]) { pos = i; flag = 0; Min = d1[x] + z + d2[y]; } if (Min > d1[y] + z + d2[x]) { pos = i; flag = 1; Min = d1[y] + z + d2[x]; } } print_path(pos, flag); if (pos == -1) printf(Ticket Not Used ); else { if (flag == 0) printf(%d , node[pos].x); else printf(%d , node[pos].y); } printf(%d , Min); } int main() { bool flag = false; while (scanf(%d%d%d, &n, &s, &e) != EOF) { if (flag) printf( ); flag = true; init(); solve(); } return 0; }