首页 > 代码库 > 1808: 地铁
1808: 地铁
1808: 地铁
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 693 Solved: 161
[Submit][Status][Web Board]
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 31 2 1 12 3 2 11 3 1 13 31 2 1 12 3 2 11 3 1 103 21 2 1 12 3 1 1Sample Output
132
思路：最短路；
这里不能够按照点来求最短路，而是按照边来求，因为有了额外花费这个条件，某一点可能经由不同的边到达，该点的最小值不仅可能由上一最小值点更新，也可能由一个大一些的点更新过来，加上额外花费之后变成了最小值点，所以不能以点建图，而应该以边建图
但每条边两端点出所要增加的价值是个定值，所以可以用最短路来求到每条边的最小值。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 #include<stack> 8 #include<vector> 9 using namespace std; 10 typedef long long LL; 11 LL d[100005]; 12 typedef struct node 13 { 14 int from; 15 int to; 16 LL cost; 17 int id; 18 LL p; 19 bool operator <(const node&cx)const 20 { 21 return cx.cost < cost; 22 } 23 } ss; 24 vector<ss>vec[100005]; 25 LL t[100005]; 26 void dj(int s); 27 int main(void) 28 { 29 int n,m; 30 while(scanf("%d %d",&n,&m)!=EOF) 31 { 32 int i,j; 33 for(i = 0; i < 100005; i++) 34 vec[i].clear(); 35 for(i = 1; i <= m; i++) 36 { 37 int a,b,c; 38 scanf("%d %d %lld %d",&a,&b,&t[i],&c); 39 ss ab; 40 ab.from = a; 41 ab.to = b; 42 ab.cost = c; 43 ab.id = i; 44 ab.p = t[i]; 45 vec[a].push_back(ab); 46 ab.to = a; 47 ab.from = b; 48 vec[b].push_back(ab); 49 } 50 if(n == 1)printf("0\n"); 51 else 52 { 53 LL maxx = 1e16; 54 dj(1); 55 for(i = 0; i < vec[n].size(); i++) 56 { 57 maxx = min(maxx,d[vec[n][i].id]); 58 } 59 printf("%lld\n",maxx); 60 } 61 } 62 return 0; 63 } 64 void dj(int s) 65 { 66 LL sum = 0; 67 fill(d,d+100005,1e16); 68 priority_queue<ss>que; 69 int i,j; 70 for(i = 0; i < vec[s].size(); i++) 71 { 72 ss ak = vec[s][i]; 73 ss ac; 74 ac.cost = ak.cost; 75 ac.from = s; 76 ac.to = ak.to; 77 ac.id = ak.id; 78 ac.p = ak.p; 79 que.push(ac); 80 d[ac.id] = ak.cost; 81 } 82 while(!que.empty()) 83 { 84 ss ak = que.top(); 85 que.pop(); 86 if(d[ak.id] < ak.cost)continue; 87 for(i = 0; i < vec[ak.to].size(); i++) 88 { 89 ss ac = vec[ak.to][i]; 90 //printf("%lld %lld %lld\n",ac.p,ak.p,ak.id); 91 if(d[ac.id] > d[ak.id] + ac.cost + abs(ac.p-ak.p)) 92 { 93 d [ac.id]= d[ak.id] + ac.cost + abs(ac.p-ak.p); 94 ss av; 95 av.from = ac.from; 96 av.to = ac.to; 97 av.cost = d[ac.id]; 98 av.p = ac.p; 99 av.id = ac.id;100 que.push(av);101 }102 }103 }104 }
1808: 地铁
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。