CSU->1808: 地铁

1808: 地铁

Time Limit: 5 Sec     Memory Limit: 128 Mb     
           

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

Hint

Source

湖南省第十二届大学生计算机程序设计竞赛

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

题解：本题应该直接把边作为研究对象。将边的信息记录到edge中（包括两端点，线路，以及通行时间）。因为edge已经包含了线路，所以松弛时（即为找最短路径时）就可以直接计算了。dist[i]记录从顶点1到顶点i的最短路径（题目中为时间）。

AC代码：

#include<iostream>
#include<queue>
#include<cmath>
#include<string.h>
#define maxn 200000
#define LNF ((1LL<<62)-1)
typedef long long ll;
using namespace std;

int n,m;
int u,v,c,t;
int vis[maxn],head[maxn],tot;       //访问，当前站点，总站数
ll dist[maxn];

struct edge{
    int v,c,t,next;
}edge[maxn];

void Init(){
    memset(head,-1,sizeof(head));
    tot=0;
}

void addEdge(int u,int v,int c,int t){      //将与u相连通的串在一起，也可以用vector
    edge[tot].v=v;
    edge[tot].c=c;
    edge[tot].t=t;
    edge[tot].next=head[u];
    head[u]=tot++;
}

ll Dijkstra(){
    //队列记录花费的时间以及当前边的编号，升序 
    priority_queue <pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q; 
    memset(vis,0,sizeof(vis));
    for(int i = 0; i<tot; i++){
        dist[i] = LNF;
    } 
    for(int i=head[1];i!=-1;i=edge[i].next){    //初始化，顶点1作为u的边入队
        dist[i]=edge[i].t;
        q.push(make_pair(dist[i],i));
    }
    while(!q.empty()){
        pair<ll,int>tmp=q.top();
        q.pop();
        int now=tmp.second;     //取边的编号
        vis[now]=1;
        int u=edge[now].v;
        if(u==n){
            return dist[now];   //如果当前边的v为顶点n，则找到最短路径
        }
        for(int i=head[u];i!=-1;i=edge[i].next){    //松弛 
            int v=edge[i].v;
            //abs（...）为转站花费的时间，如果相同，即为0
            if(!vis[i]&&dist[i]>dist[now]+edge[i].t+abs(edge[i].c-edge[now].c)){
                dist[i]=dist[now]+edge[i].t+abs(edge[i].c-edge[now].c);
                q.push(make_pair(dist[i],i));
            }
        }
    }
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        Init();
        for(int i=0;i<m;i++){
            scanf("%d%d%d%d",&u,&v,&c,&t);
            addEdge(u,v,c,t);
            addEdge(v,u,c,t);
        }
        cout<<Dijkstra()<<endl;
    }   
    return 0;
}