首页 > 代码库 > CSU 1808 地铁
CSU 1808 地铁
湖南省第十二届大学生计算机程序设计竞赛$F$题。
最短路。
如果只记录到某个节点的最短路，显然是错误的。这题的状态有两个量决定，即到了哪一个节点，最后一辆乘坐的是几号线。这个可以用$map$记录一下。
要注意的是：如果用$SPFA$，因为要标记某个状态是否在队列中，还需要额外开一个$map$，这样可能导致超时；用$dijkstra$$+$优先队列优化的话就可以通过。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}const LL INF=(LL)1e17;const int maxn=200010;struct Edge{ int u,v,c; LL t; int nx;}e[maxn];int h[maxn],sz;int n,m;LL ans[maxn];void add(int u,int v,int c,LL t){ e[sz].u=u; e[sz].v=v; e[sz].c=c; e[sz].t=t; e[sz].nx=h[u]; h[u]=sz++;}struct Node{ int p,id; LL dis; Node(int P,int ID,LL DIS) { dis=DIS, p=P, id=ID; } bool operator < (const Node &a) const { if(dis==a.dis&&p==a.p) return id>a.id; if(dis==a.dis) return p>a.p; return dis>a.dis; }};struct X{ int p,id; X (int P,int ID) { p=P, id=ID; } bool operator < (const X &a) const { if(p==a.p) return id>a.id; return p>a.p; }};LL ABS(LL a) { if(a>=0) return a; return -a; }void dij(){ map<X,LL>f; priority_queue<Node>Q; Q.push(Node(1,0,0)); for(int i=1;i<=n;i++) ans[i]=INF; ans[1]=0; while(!Q.empty()) { Node top=Q.top(); Q.pop(); ans[top.p]=min(ans[top.p],top.dis); if(top.dis>f[X(top.p,top.id)]) continue; for(int i=h[top.p];i!=-1;i=e[i].nx) { LL COST; if(top.p==1) COST=0; else COST=ABS((LL)e[i].c-(LL)top.id); LL pp=f[X(e[i].v,e[i].c)]; if((pp==0&&e[i].v!=1)||top.dis+COST+e[i].t<pp) { f[X(e[i].v,e[i].c)]=top.dis+COST+e[i].t; Q.push(Node(e[i].v,e[i].c,top.dis+COST+e[i].t)); } } }}int main(){ while(~scanf("%d%d",&n,&m)) { memset(h,-1,sizeof h); sz=0; for(int i=1;i<=m;i++) { int u,v,c; LL t; scanf("%d%d%d%lld",&u,&v,&c,&t); add(u,v,c,t); add(v,u,c,t); } dij(); cout<<ans[n]<<endl; } return 0;}
CSU 1808 地铁
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。