题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1808

题意：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 所需要花费的最小时间。

解法：

这题如果把点当作状态的话有些不妥

其实这题因为有了额外花费这个条件，应该把边当作状态

dis[i]表示走过i这条边打到edge[i].v的最少花费

这样的话就2∗m条边

把边看作点来做最短路，但是这题的边数未知

所以spfa会TLE，所以要用dijkstra+heap

在写的过程中，发现了之前一个没注意的问题，pair

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
#define mp(x,y) make_pair(x,y)
const int maxn = 500010;
int head[maxn], edgecnt;
void init(){
    memset(head, -1, sizeof(head));
    edgecnt=0;
}
struct edge{
    int v,next,num,c;
}E[maxn*2];
void add(int u, int v, int num, int c){
    E[edgecnt].v=v,E[edgecnt].next=head[u],E[edgecnt].num=num,E[edgecnt].c=c;
    head[u]=edgecnt++;
}
LL dis[maxn];//经过第i条边，到达E[i].v的最小花费
bool vis[maxn];

LL Dij(int s, int t){
    priority_queue<pii,vector<pii>,greater<pii> >q;
    //pair<int,LL> 边和距离值
    for(int i=0; i<edgecnt; i++) dis[i]=1e18, vis[i]=0;
    for(int i=head[s]; ~i; i=E[i].next){
        dis[i]=E[i].c;
        q.push(mp(E[i].c,i));
    }
    LL ans=1e18;
    while(!q.empty()){
        pii x=q.top(); q.pop();
        int p = x.second;
        if(vis[p]) continue;
        vis[p]=1;
        int u=E[p].v;
        if(u==t){
            ans = min(ans, dis[p]);
        }
        for(int i=head[u]; ~i; i=E[i].next){
            if(!vis[i]&&dis[i]>dis[p]+E[i].c+abs(E[i].num-E[p].num)){
                dis[i]=dis[p]+E[i].c+abs(E[i].num-E[p].num);
                q.push(mp(dis[i],i));
            }
        }
    }
    return ans;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=1; i<=m; i++){
            int a,b,c,t;
            scanf("%d%d%d%d",&a,&b,&c,&t);
            add(a,b,c,t);
            add(b,a,c,t);
        }
        LL ans=Dij(1,n);
        printf("%lld\n", ans);
    }
    return 0;
}