首页 > 代码库 > CSU 1808 地铁
CSU 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 所需要花费的最小时间。
分析：
很明显的最短路，但是有两个做法.
一是按每个站点有几个地铁经过然后拆为多个点。然后两次添加边，第一次是添加不同站点之间的花费，第二次是是相同站点不同地铁线路的话费。
二是把边当做状态dist[i]表示走过i这条边打到edge[i].v的最少花费，这样的话就2∗m条边
spfa会TLE，所以要用dijkstra+heap
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
方法一：
#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<map>#include<queue>#include<algorithm>using namespace std;const int maxn =255555;const int INF = 0x3f3f3f3f;int n,m;struct Edge{ int to,next; int w;}edge[maxn*2];int head[maxn],tot;void init(){ memset(head,-1,sizeof(head)); tot=0;}void addedge(int u,int v,int w){ edge[tot].to=v; edge[tot].next = head[u]; edge[tot].w =w; head[u]=tot++;}vector<int>num[maxn];//存贮第i个站点跟哪几个地铁相连map<int,int>mp[maxn];//存贮第i个站点跟几个地铁相连int dis[maxn];int cnt;struct node{ int now; int c; node(int _now = 0,int _c=0):now(_now),c(_c){} bool operator <(const node &r)const { return c>r.c; }};void DJ(){ priority_queue<node> que; while(!que.empty()) que.pop(); for(int i=1;i<cnt;++i) dis[i]=INF; for(int i=0;i<num[1].size();++i){ int st; st = mp[1][num[1][i]]; dis[st]=0; que.push(node(st,0)); } node temp; while(!que.empty()){ temp = que.top(); que.pop(); int u = temp.now; int cost = temp.c; if(cost>dis[u]) continue; for(int i=head[u];~i;i=edge[i].next){ int v = edge[i].to; int w = edge[i].w; if(dis[v]>cost+w){ dis[v]= cost + w; que.push(node(v,dis[v])); } } }}int main(){ int u,v,w,x; while(scanf("%d%d",&n,&m)!=EOF){ init(); cnt=1; for(int i=1;i<=n;i++){ num[i].clear(); mp[i].clear(); } for(int i=0;i<m;++i){ scanf("%d%d%d%d",&u,&v,&x,&w); if(!mp[u][x]){ mp[u][x]=cnt++; num[u].push_back(x); } u=mp[u][x]; if(!mp[v][x]){ mp[v][x]=cnt++; num[v].push_back(x); } v=mp[v][x]; addedge(u,v,w); addedge(v,u,w); } for(int i=1;i<=n;i++){ sort(num[i].begin(),num[i].end()); for(int j=0;j<num[i].size()-1;++j){ u=mp[i][num[i][j]]; v=mp[i][num[i][j+1]]; w=num[i][j+1]-num[i][j]; //同一站点不同线路的拆点之间的差值 addedge(u,v,w); addedge(v,u,w); } } DJ(); int ans=INF; for(int i=0;i<num[n].size();i++){ u=mp[n][num[n][i]]; ans=min(ans,dis[u]); } printf("%d\n",ans); } return 0;}
方法二：
#include <map>#include <set>#include <stack>#include <queue>#include <cmath>#include <string>#include <vector>#include <cstdio>#include <cctype>#include <cstring>#include <sstream>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define MAX 100005#define MAXN 1000005#define LL long longinline void RI(int &x) { char c; while((c=getchar())<‘0‘ || c>‘9‘); x=c-‘0‘; while((c=getchar())>=‘0‘ && c<=‘9‘) x=(x<<3)+(x<<1)+c-‘0‘; }struct Edge{ int v,next,num,c;}edge[MAX*2];struct Node{ int id,val; bool operator<(const Node &a)const{ return val>a.val; }}x;int head[MAX];LL dis[MAX*2];int vis[MAX*2];int tot;void add_edge(int a,int b,int c,int d){ edge[tot]=(Edge){b,head[a],c,d}; head[a]=tot++; edge[tot]=(Edge){a,head[b],c,d}; head[b]=tot++;}LL dijkstra(int s,int t){ priority_queue<Node> q; for(int i=0;i<tot;i++){ dis[i]=1e18; vis[i]=0; } for(int i=head[s];i!=-1;i=edge[i].next){ x=(Node){i,edge[i].c}; dis[i]=edge[i].c; q.push(x); } LL ans=1e18; while(!q.empty()){ x=q.top(); q.pop(); int p=x.id; if(vis[p]) continue; vis[p]=1; int u=edge[p].v; if(u==t) ans=min(ans,dis[p]); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(!vis[i]&&dis[i]>dis[p]+edge[i].c+abs(edge[i].num-edge[p].num)){ dis[i]=dis[p]+edge[i].c+abs(edge[i].num-edge[p].num); q.push((Node){i,dis[i]}); } } } return ans;}int main() { int n,m; while(cin>>n>>m){ tot=0; for(int i=1;i<=n;i++) head[i]=-1; for(int i=0;i<m;i++){ int a,b,c,d; RI(a);RI(b);RI(c);RI(d); add_edge(a,b,c,d); } cout<<dijkstra(1,n)<<endl; } return 0;}
dis[i]表示走过i这条边打到edge[i].v的最少花费
这样的话就2∗m条边
把边看作点来做最短路，但是这题的边数未知
所以spfa会TLE，所以要用dijkstra+heap
CSU 1808 地铁
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。