首页 > 代码库 > UVa 11374 机场快线
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的时间。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7 8 const int INF = 1000000000; 9 const int maxn = 500 + 5; 10 11 struct Edge 12 { 13 int from, to, dist; 14 Edge(int u, int v, int d) :from(u), to(v), dist(d){} 15 }; 16 17 struct HeapNode 18 { 19 int d, u; 20 HeapNode(int x, int y) :d(x), u(y){} 21 bool operator < (const HeapNode& rhs) const{ 22 return d > rhs.d; 23 } 24 }; 25 26 struct Dijkstra 27 { 28 int n, m; //点数和边数 29 vector<Edge> edges; //边列表 30 vector<int> G[maxn]; //每个结点出发的边编号（从0开始编号） 31 bool done[maxn]; //是否已永久标号 32 int d[maxn]; //s到各个点的距离 33 int p[maxn]; //最短路中的上一条边 34 35 void init(int n) 36 { 37 this->n = n; 38 for (int i = 0; i < n; i++) G[i].clear(); 39 edges.clear(); 40 } 41 42 void AddEdges(int from, int to, int dist) 43 { 44 edges.push_back(Edge(from,to,dist)); 45 m = edges.size(); 46 G[from].push_back((m - 1)); 47 } 48 49 void dijkstra(int s) 50 { 51 priority_queue<HeapNode> Q; 52 for (int i = 0; i < n; i++) d[i] = INF; 53 d[s] = 0; 54 memset(done, 0, sizeof(done)); 55 Q.push(HeapNode(0,s)); 56 while (!Q.empty()) 57 { 58 HeapNode x = Q.top(); Q.pop(); 59 int u = x.u; 60 if (done[u]) continue; 61 done[u] = true; 62 for (int i = 0; i < G[u].size(); i++) 63 { 64 Edge& e = edges[G[u][i]]; 65 if (d[e.to] > d[u] + e.dist) 66 { 67 d[e.to] = d[u] + e.dist; 68 p[e.to] = e.from; 69 Q.push(HeapNode(d[e.to],e.to)); 70 } 71 } 72 } 73 } 74 75 void getpath(int s, int e, vector<int>& path) 76 { 77 int pos = e; 78 while (true) 79 { 80 path.push_back(pos); 81 if (pos == s) 82 break; 83 pos = p[pos]; 84 } 85 } 86 87 }t[2]; 88 89 int N, S, E; 90 vector<int> path; 91 92 int main() 93 { 94 //freopen("D:\\input.txt", "r", stdin); 95 int time, kase = 0; 96 while (scanf("%d%d%d", &N, &S, &E) != EOF) 97 { 98 S--; E--; 99 if (kase != 0) printf("\n");100 kase++;101 t[0].init(N);102 t[1].init(N);103 path.clear();104 int M, K;105 int u, v, d;106 scanf("%d", &M);107 while (M--)108 {109 scanf("%d%d%d", &u, &v, &d); 110 u--; v--;111 t[0].AddEdges(u, v, d);112 t[1].AddEdges(u, v, d);113 t[0].AddEdges(v, u, d);114 t[1].AddEdges(v, u, d);115 }116 t[0].dijkstra(S);117 t[1].dijkstra(E);118 int ks = -1, ke = -1;119 time = t[0].d[E];120 scanf("%d", &K);121 while (K--)122 {123 scanf("%d%d%d", &u, &v, &d);124 u--;v--;125 if (d + t[0].d[u] + t[1].d[v] < time){126 time = d + t[0].d[u] + t[1].d[v];127 ks = u; ke = v;128 }129 if (d + t[0].d[v] + t[1].d[u] < time){130 time = d + t[0].d[v] + t[1].d[u];131 ks = v; ke = u;132 }133 }134 if (ks == -1)135 {136 t[0].getpath(S, E, path);137 reverse(path.begin(), path.end());138 for (int i = 0; i < path.size() - 1; i++)139 printf("%d ", path[i]+1);140 printf("%d\n", E+1);141 printf("Ticket Not Used\n");142 printf("%d\n", time);143 }144 else145 {146 t[0].getpath(S, ks, path);147 reverse(path.begin(), path.end());148 t[1].getpath(E, ke, path);149 for (int i = 0; i < path.size() - 1; i++)150 printf("%d ", path[i]+1 );151 printf("%d\n", E+1);152 printf("%d\n", ks + 1);153 printf("%d\n", time);154 }155 }156 return 0;157 }
UVa 11374 机场快线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。