1808: 地铁
Description
Bobo 居住在大城市 ICPCCamp。
ICPCCamp 有 n 个地铁站，用 1,2,…,n 编号。 m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于 ci 号线，位于站 ai,bi 之间，往返均需要花费 ti 分钟（即从 ai 到 bi 需要 ti 分钟，从 bi 到 ai 也需要 ti 分钟）。
众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费 |ci-cj | 分钟。注意，换乘只能在地铁站内进行。
Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。
Input
输入包含不超过 20 组数据。
每组数据的第一行包含两个整数 n,m (2≤n≤105,1≤m≤105).
接下来 m 行的第 i 行包含四个整数 ai,bi,ci,ti (1≤ai,bi,ci≤n,1≤ti≤109).
保证存在从地铁站 1 到 n 的地铁线路（不一定直达）。
Output
对于每组数据，输出一个整数表示要求的值。
Sample Input
3 3
1 2 1 1
2 3 2 1
1 3 1 1
3 3
1 2 1 1
2 3 2 1
1 3 1 10
3 2
1 2 1 1
2 3 1 1
Sample Output
1
3
2
题解：
现在假设i号线在深度i的世界里跑
换线相当于换层
然后换乘站相当于一个垂直通道，拆出一些点放到对应的层里
然后按照深度从小到大连……
你从1楼上到3楼就和你从1楼上到2楼，再从2楼上到3楼是一样的
连边侯跑一发最短路就好了 ，spfa超时
感谢quailty的题解和代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
typedef long long LL;
const LL INF = (1LL<<)-;
const double Pi = acos(-1.0);
const int N = 1e5+, M = 1e6+, mod = 1e9+, inf = (<<)-; LL dist[N<<];
int vis[N<<];
struct Edge
{
int a,b,t;
Edge(int _a=,int _b=,int _t=) : a(_a), b(_b), t(_t) {}
};
struct qnode {
LL v,c;
qnode(LL _v=,LL _c=) : v(_v), c(_c) {}
bool operator < (const qnode &r) const
{
return c > r.c;
}
};
vector< Edge > tmp[N<<];
vector< pair<int,int > > G[N<<];
vector<pair<int ,int > > p[N<<];
void Add(int u,int v,int w) {
G[u].push_back(make_pair(v,w));
G[v].push_back(make_pair(u,w));
}
void init() {
for(int i = ; i < N; ++i) p[i].clear(), tmp[i].clear();
for(int i = ; i < * N; ++i) G[i].clear();
}
void Dij(int n,int u) {
for(int i = ; i <= n; ++i) dist[i] = INF, vis[i] = ;
priority_queue<qnode> q;
for(int i = ; i < p[u].size(); ++i) {
dist[p[u][i].first] = ;
q.push(qnode{p[u][i].first,});
}
while(!q.empty()) {
int k = q.top().v;
q.pop();
if(vis[k]) continue;
vis[k] = ;
for(int i = ; i < G[k].size(); ++i)
{
int v = G[k][i].first;
int c = G[k][i].second;
if(!vis[v] && dist[v] > dist[k] + c) {
dist[v] = dist[k] + c;
q.push(qnode{v,dist[v]});
}
}
}
}
int n,m;
int main() {
while(scanf("%d%d",&n,&m)!=EOF) {
init();
for(int i = ; i <= m; ++i) {
int a,b,c,t;
scanf("%d%d%d%d",&a,&b,&c,&t);
tmp[c].push_back(Edge(a,b,t));
}
int tot = ;
for(int i = ; i < N; ++i) {
for(int j = ; j < tmp[i].size(); ++j) {
int v[] = {tmp[i][j].a,tmp[i][j].b}, w = tmp[i][j].t;
for(int _=;_<;++_){
int u = v[_];
if(p[u].empty() || p[u].back().second < i) {
p[u].push_back(make_pair(++tot,i));
int s = p[u].size();
if(s > ) Add(p[u][s-].first,p[u][s-].first,p[u][s-].second-p[u][s-].second);
}
}
Add(p[v[]].back().first,p[v[]].back().first,w);
}
}
Dij(tot,);
LL ans = INF;
for(int i = ; i < p[n].size(); ++i)
ans = min( ans, dist[p[n][i].first]);
printf("%lld\n",ans);
}
return ;
}