题目链接

题意：在Iokh市中，机场快线是市民从市内去机场的首选交通工具。机场快线分为经济线和商业线两种，线路，速度和价钱都不同。你有一张商业线车票，可以做一站商业线，而其他时候只能乘坐经济线。假设换乘时间忽略不计，你的任务是找一条去机场最快的路线。。

solution：dijkstra/spfa预处理出每个点到起点和终点的距离，再枚举商业线，复杂度O（mlogn+k）

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define Inf 0x3f3f3f3f
const int N = 505;int n, ans, S, E;
int d1[N], d2[N], p1[N], p2[N];
struct Edge{int u, v, w;Edge(int u, int v, int w):u(u),v(v),w(w){}
};
struct HeapNode{int dist, u;bool operator<(const HeapNode& rhs) const{return dist>rhs.dist;}
};
struct Dijkstra{int n;int d[N], p[N];bool vis[N];vector<Edge>edges;vector<int>G[N]; void init(int n){this->n=n;for ( int i=1; i<=n; i++ ) G[i].clear();edges.clear();}void addeage(int u, int v, int w){edges.push_back((Edge){u,v,w});int m=edges.size();G[u].push_back(m-1);}void dijkstra(int s){for ( int i=1; i<=n; i++ ) d[i]=Inf, p[i]=0;memset(vis,0,sizeof(vis));priority_queue<HeapNode> Q;Q.push((HeapNode){
   0,s});d[s]=0;while( !Q.empty() ){HeapNode x=Q.top(); Q.pop();int u=x.u;if( vis[u] ) continue;vis[u]=1;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];if( d[e.v] > d[u]+e.w ){d[e.v]=d[u]+e.w;p[e.v]=e.u;Q.push((HeapNode){d[e.v],e.v});}}}}};struct SPFA{int n;vector<Edge> edges;vector<int> G[N];int d[N], p[N];bool inq[N];void init(int n){this->n=n;for ( int i=1; i<=n; i++ ) G[i].clear();edges.clear();}void addeage(int u, int v, int w){edges.push_back((Edge){u,v,w});int m=edges.size();G[u].push_back(m-1);}void spfa(int s){for ( int i=1; i<=n; i++ ) d[i]=Inf, inq[i]=false, p[i]=0;queue<int> Q;Q.push(s);d[s]=0;inq[s]=true;while( !Q.empty() ){int u=Q.front(); Q.pop();inq[u]=false;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];if( d[e.v]>d[u]+e.w ){d[e.v]=d[u]+e.w;p[e.v]=u;if( !inq[e.v] ){inq[e.v]=true;Q.push(e.v); } }}}}
};
SPFA solve;inline int read(){int x=0, f=1; char ch=getchar();while( !isdigit(ch) ) { if(ch=='-') f=-1; ch=getchar(); }while( isdigit(ch) ) { x=x*10+ch-'0'; ch=getchar(); }return x*f;
} void ptX(int u){if( u==S ){printf("%d", u );return ;}ptX(p1[u]);printf(" %d", u);
}
void ptY(int u){printf(" %d", u );if( u==E ) return ;ptY(p2[u]);
}
int main(){//freopen("1.cpp","w",stdout);int k=0;while( scanf("%d%d%d", &n, &S, &E)==3 ){if( k++ ) printf("\n");solve.init(n);int m;
// m=read();scanf("%d", &m);for ( int i=1; i<=m; i++ ){int x, y, z;// x=read(), y=read(), z=read();scanf("%d%d%d", &x, &y, &z );solve.addeage(x,y,z), solve.addeage(y,x,z);}solve.spfa(S);for ( int i=1; i<=n; i++ ) d1[i]=solve.d[i], p1[i]=solve.p[i];solve.spfa(E);for ( int i=1; i<=n; i++ ) d2[i]=solve.d[i], p2[i]=solve.p[i];// m=read();scanf("%d", &m);int X=0, Y=0; ans=d1[E];for ( int i=1; i<=m; i++ ){int x, y, z;//x=read(), y=read(), z=read();scanf("%d%d%d", &x, &y, &z );if( d1[x]+d2[y]+z < ans ){ans=d1[x]+d2[y]+z;X=x, Y=y;}if( d1[y]+d2[x]+z < ans ){ans=d1[y]+d2[x]+z;X=y, Y=x;} }// printf("%d %d\n", X, Y);if( X!=Y ) {ptX(X), ptY(Y); printf("\n");printf("%d\n", X);printf("%d\n", ans);}else{ptX(E);printf("\n");printf("Ticket Not Used\n");printf("%d\n", ans);}}
}