题意：在Iokh市中，机场快线是市民从市内去机场的首选交通工具。机场快线分为经济线和商业线两种，线路，速度和价钱都不同。你有一张商业线车票，，可以做一站商业线，而其他时候只能乘坐经济线。假设换乘时间忽略不计，你的任务是找一条去机场最快的路线。。
分析:枚举商业线T(a,b),则总时间为f(a)+T(a,b)+g(b);f和g用两次dijkstra来计算，以S为起点的dijkstra和以E为起点的dijkstra；
注意：有可能只做慢车到达不了终点，这时必须做某站快车，如果按照坐慢车一定能到达终点然后从起点打印路径可能会出错,因为此时没有一条完整路径，这时从换到的站到终点应从另一侧打印
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>#define eps 1e-6 #define LL long long using namespace std; const int maxn = 550;const int INF = 100000000;int N, S, E, M, K;vector<pair<int, int> > kuai[maxn];int kase;//Dijkstra struct Edge {int from, to, dist;Edge(int u = 0, int v = 0, int d = 0) : from(u), to(v), dist(d) {}};struct HeapNode {///用到的优先队列的结点 int d, u;bool operator < (const HeapNode& rhs) const {return d > rhs.d;}};struct Dijkstra {int n, m; //点数和边数vector<Edge> edges; //边列表 vector<int> G[maxn];//每个节点出发的边编号 bool done[maxn];//是否已经永久编号int d[maxn];//s到各个点的距离int p[maxn];//最短路中的上一条边void init(int n) {this->n = n;for(int i = 0; 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-1);}void dijkstra(int s) {//求s到所有点的距离,0表示起点，1表示终点 priority_queue<HeapNode> Q;for(int i = 0; i < n; i++) d[i] = INF;d[s] = 0;memset(done, 0, sizeof(done));Q.push((HeapNode){0, s});while(!Q.empty()) {HeapNode x = Q.top(); Q.pop();int u = x.u;if(done[u]) continue;done[u] = true;for(int i = 0; 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((HeapNode){d[e.to], e.to});}}}}void dfs(int S, int E) {if(S == E) {printf("%d", E+1);return;}int u = p[E];int v = edges[u].from;dfs(S, v);printf(" %d", E+1);}} Dij[2];void init() {S–; E–;cin >> M;int u, v, dist;Dij[0].init(N);Dij[1].init(N);for(int i = 0; i < N; i++) kuai[i].clear();for(int i = 0; i < M; i++) {scanf("%d%d%d", &u, &v, &dist);u–; v–;Dij[0].AddEdge(u, v, dist); Dij[1].AddEdge(u, v, dist);Dij[0].AddEdge(v, u, dist); Dij[1].AddEdge(v, u, dist);}Dij[0].dijkstra(S);Dij[1].dijkstra(E);cin >> K;for(int i = 0; i < K; i++) {scanf("%d%d%d", &u, &v, &dist);u–; v–;kuai[u].push_back(make_pair(v, dist));kuai[v].push_back(make_pair(u, dist));}}void solve() {if(kase) cout << endl;kase++; int ans = INF, huancheng, huandao;for(int i = 0; i < N; i++) {int sz = kuai[i].size();for(int j = 0; j < sz; j++) {if(ans > Dij[0].d[i]+Dij[1].d[kuai[i][j].first]+kuai[i][j].second) {huancheng = i; huandao = kuai[i][j].first;ans = Dij[0].d[i]+Dij[1].d[kuai[i][j].first]+kuai[i][j].second;}} }if(ans > Dij[0].d[E]) {Dij[0].dfs(S, E);cout << endl;cout << "Ticket Not Used" << endl;cout << Dij[0].d[E] << endl;}else {Dij[0].dfs(S, huancheng);int pos = huandao;while(pos != E) {printf(" %d", pos+1);pos = Dij[1].edges[Dij[1].p[pos]].from;}printf(" %d\n", E+1);cout << huancheng+1 << endl;cout << ans << endl;}}int main() {//freopen("input.txt", "r", stdin);while(scanf("%d%d%d", &N, &S, &E) == 3) {init();solve();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
不敢面对自己的不完美，总是担心自己的失败，
