题目链接：
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1808
1808: 地铁
Time Limit: 5 SecMemory Limit: 128 MB
#### 问题描述
> 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 所需要花费的最小时间。
#### 输入
> 输入包含不超过 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 的地铁线路（不一定直达）。
#### 输出
> 对于每组数据，输出一个整数表示要求的值。
#### 样例
> **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
题解
一个地铁站有多少条线路，就把它拆成多少个点，然后对地铁线路编号相邻的两个点建边，权值为编号差值的绝对值，（由于权值的计算方式比较特殊，我们没有必要连成完全图，只需要连一条链就可以了。）图建完后跑最短路径。
代码
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=4e5+10;
int n,m,tot;
struct Node{
int id,u,v,w;
}nds[maxn];
struct Edge{
int u,v,w;
Edge(int u,int v,int w):u(u),v(v),w(w){}
};
struct HeapNode{
LL d; int u;
HeapNode(LL d,int u):d(d),u(u){}
bool operator < (const HeapNode& rhs) const {
return d>rhs.d;
}
};
struct Dijkstra{
int n,m;
vector<Edge> egs;
vector<int> G[maxn];
bool done[maxn];
LL d[maxn];
void init(int n){
this->n=n;
rep(i,0,n) G[i].clear();
egs.clear();
}
void addEdge(int u,int v,int d){
egs.pb(Edge(u,v,d));
m=egs.sz();
G[u].pb(m-1);
}
void dijkstra(VI &lis){
priority_queue<HeapNode> Q;
rep(i,0,n) d[i]=INFL;
rep(i,0,lis.sz()){
int v=lis[i];
d[v]=0;
Q.push(HeapNode(0,v));
}
clr(done,0);
while(!Q.empty()){
HeapNode x=Q.top(); Q.pop();
int u=x.u;
if(done[u]) continue;
done[u]=true;
rep(i,0,G[u].sz()){
Edge& e=egs[G[u][i]];
if(d[e.v]>d[u]+e.w){
d[e.v]=d[u]+e.w;
Q.push(HeapNode(d[e.v],e.v));
}
}
}
}
}dij;
map<pair<int,int>,int> mp;
VI G[maxn];
void init(){
mp.clear();
rep(i,0,n+10) G[i].clear();
tot=0;
}
int main() {
while(scf("%d%d",&n,&m)==2){
init();
rep(i,0,m){
scf("%d%d%d%d",&nds[i].u,&nds[i].v,&nds[i].id,&nds[i].w);
G[nds[i].u].pb(nds[i].id);
G[nds[i].v].pb(nds[i].id);
}
for(int i=1;i<=n;i++){
sort(all(G[i]));
G[i].erase(unique(all(G[i])),G[i].end());
rep(j,0,G[i].sz()){
int v=G[i][j];
mp[mkp(i,v)]=tot++;
}
}
dij.init(tot);
rep(i,0,m){
int u=mp[mkp(nds[i].u,nds[i].id)];
int v=mp[mkp(nds[i].v,nds[i].id)];
dij.addEdge(u,v,nds[i].w);
dij.addEdge(v,u,nds[i].w);
}
for(int i=1;i<=n;i++){
rep(j,0,G[i].sz()-1){
int u=mp[mkp(i,G[i][j])];
int v=mp[mkp(i,G[i][j+1])];
int w=G[i][j+1]-G[i][j];
dij.addEdge(u,v,w);
dij.addEdge(v,u,w);
}
}
VI lis;
rep(i,0,G[1].sz()){
int v=mp[mkp(1,G[1][i])];
lis.pb(v);
}
dij.dijkstra(lis);
LL ans=INFL;
rep(i,0,G[n].sz()){
int v=mp[mkp(n,G[n][i])];
ans=min(ans,dij.d[v]);
}
prf("%lld\n",ans);
}
return 0;
}
//end-----------------------------------------------------------------------
1808: 地铁