首页 » 未分类 » 正文

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

来源:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=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

Hint

Source

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

总结

使用SPFA做的,最开始想的一个个点的走过去,其间不断地加上换乘后的新路径时间和两条路径的c的差值,WA了两发,想了下发现到达一个点的下一个节点最短的路径所包含的路径不一定是当前点最短路径所包含的路径。
我采取计算通过每条边所到达某点的最短距离来剪枝,用dis[] 数组来保存通过该边到达该边终点的最短距离,并将该状态放入优先队列中,最终通过判断具有最短路径的边的终点是否为n来结束循环。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long 
using namespace std;  

const int INF = 0x7f7f7f7f;  
const int  MAXN = 100100;  
const int MAXM = 200100;    
int head[MAXN];
int Next[MAXM];  
ll dis[MAXM];  
struct note{
    int u,v,c,t;  
    note(){} 
    note(int u, int v, int c, int t):u(u), v(v), c(c), t(t){}
} p[MAXM];

template<class T>
inline bool scan_d(T &ret){  //读入挂 
    char c;  int sgn;  
    if( c = getchar(), c==EOF) return 0;  
    while(c!='-' && (c <'0' || c>'9'))c = getchar();  
    sgn = (c=='-') ?-1:1; 
    ret = (c == '-')?0:(c-'0');  
    while(c = getchar(), c>='0' && c<='9') ret = ret*10+(c-'0');  
    ret *= sgn;  
    return 1;  
}

inline void out(int x){  //输出挂 
    if(x > 9) out(x/10);  
    putchar(x%10+'0');  
}
int e,n,m;  
inline void addnote(int u, int v, int c, int t){
    p[e]=note(u,v,c,t);  
    Next[e] = head[u];  
    head[u] = e++;  
}

inline bool relax(int bian, int xinbian, ll shijian){
    if(dis[xinbian] >= shijian + abs(p[bian].c-p[xinbian].c) + p[xinbian].t){
        dis[xinbian] = shijian + abs(p[bian].c-p[xinbian].c) + p[xinbian].t;
        return true;  
    }
    //if(dis[v] >=  shijian + c - 25 )return true;  
    return false;  
}

inline void init(){
    memset(head, -1, sizeof(head));  
    memset(Next, -1, sizeof(Next));  
    e=0;  
    for(int i=0; i<m; i++){
        int u, v, c,t;  
        scan_d(u);scan_d(v); scan_d(c);  scan_d(t);   
        addnote(u,v,c, t);  
        addnote(v,u,c, t);  
    }
}

struct jiedian{
    int bian;  ll shijian;  //边号及通过该边的最短时间 
    jiedian(){}  
    jiedian(int bian,  ll shijian):bian(bian), shijian(shijian){}
    bool operator < (const jiedian &a)const{  //重载小于号 
        return shijian > a.shijian;   
    }
};

inline ll spfa(int src){
    for(int i=0; i<=2*m; i++)  //初始化 
        dis[i] = INF;  
    priority_queue<jiedian>que;  //定义优先队列 
    for(int i=head[src]; i+1; i=Next[i]){  //从起点出发的所有边算一下 
        dis[i]=p[i].t;  
        que.push(jiedian(i,p[i].t));  
    }
    while(!que.empty()){
        struct jiedian now = que.top();  
        int bian = now.bian;  
        int v = p[bian].v;  
        ll shijian = now.shijian;  
        if(p[bian].v == n) return shijian;  //已经找到权值最小的时间 
        que.pop();  //出队 
        for(int i=head[v]; i+1; i=Next[i]){  //从边所到达的点向外拓展 
            if(relax(bian, i, shijian) ){  //能否换乘 
                que.push(jiedian(i, dis[i]));  
            }
        }
    }
    return 0;  
}

int main(){
    //freopen("3.txt", "r", stdin);  
    while(scan_d(n)){
        scan_d(m);  
        init();  //初始化,读入数据 
        printf("%lld\n", spfa(1)); 

    }
}

发表评论

+ 87 = 91