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
对于每组数据，输出一个整数表示要求的值。
题解：分层图最短路。
每个地铁站按地铁线拆成若干站，这若干站之间按线号从小到大连，表示换乘地铁线。
#include <bits/stdc++.h>
using namespace std;
#define gg puts("gg");
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define pli pair<ll, int>
#define fi first
#define se second
const int N = 1e5+;
const ll inf = 1e16;
int n, m, tot;
struct edge{
int to, w;
edge(int to, int w):to(to), w(w){}
edge(){}
};
struct Edge{
int f, to, w;
Edge(int f, int to, int w): f(f), to(to), w(w){}
Edge(){}
};
vector<Edge> s[N];
vector< pii > newv[N];
vector<edge> ve[N*];////
ll d[N*];
void dijsktra(int n, int s){
for(int i = ; i <= n; i++) d[i] = inf;
priority_queue< pli, vector<pli>, greater< pli > > Q;
for(int i = ; i < newv[s].size(); i++){
int u = newv[s][i].se;
d[u] = ;
Q.push( mp(, u) );
}
while(!Q.empty()){
pli f = Q.top();
Q.pop();
ll dis = f.fi;
int x = f.se;
if(d[x] < dis)
continue ;
for(int i = ; i < ve[x].size(); i++){
int to = ve[x][i].to, w = ve[x][i].w;
if(d[to] > dis+w){
d[to] = dis+w;
Q.push( mp(d[to], to) );
}
}
}
} int main(){
int u, v;
while(~scanf("%d%d", &n, &m)){
int a, b, c, t;
for(int i = ; i < m; i++){
scanf("%d%d%d%d", &a, &b, &c, &t);
s[c].push_back( Edge(a, b, t) );
} tot = ;
for(int i = ; i <= n; i++){
for(int j = ; j < s[i].size(); j++){
int u = s[i][j].f, v = s[i][j].to, w = s[i][j].w;
if(newv[u].empty()||newv[u].back().first < i) newv[u].push_back( mp(i, ++tot) );
if(newv[v].empty()||newv[v].back().first < i) newv[v].push_back( mp(i, ++tot) );
int uu = newv[u].back().se, vv = newv[v].back().se;
ve[uu].push_back( edge(vv, w) );
ve[vv].push_back( edge(uu, w) );
}
}
for(int i = ; i <= n; i++){
for(int j = ; j < newv[i].size(); j++){
int u = newv[i][j-].se, v = newv[i][j].se, w = newv[i][j].fi-newv[i][j-].fi;
ve[u].push_back( edge(v, w) );
ve[v].push_back( edge(u, w) );
}
} dijsktra(tot, );
ll ans = inf;
for(int i = ; i < newv[n].size(); i++){
int x = newv[n][i].se;
ans = min(ans, d[x]);
}
printf("%lld\n", ans); for(int i = ; i <= n; i++){
s[i].clear();
newv[i].clear();
}
for(int i = ; i <= tot; i++)
ve[i].clear();
}
return ;
}