首页 > 代码库 > CSU 1333: Funny Car Racing 最短路
CSU 1333: Funny Car Racing 最短路
题目连接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1333
题意:给你一个n个顶点,m条边(每条边都有三个参数,开放时间,关闭时间,和通过这条边的时间)的有向图;
要你求从s 到 t 的最短路;dijkstra算法可解;
坑点:我用的是队列优化+Vector存储每条边; 在每次调用dijkstra后,必须初始化邻接表,在这个地方坑了好久,这是第二次了,以后记住 如果用vector就要初始化~
附上代码:
#include <iostream> #include <stdio.h> #include <string> #include <string.h> #include <vector> #include <queue> const int INF=999999999; using namespace std; typedef pair<int ,int > P; int n,m,s,t; struct edge { int to; int open; int close; int cost; }; vector<edge>G[330]; int d[330]; void init() { for(int i=0;i<330;i++)G[i].clear(); } void dijkstra() { priority_queue<P,vector<P>,greater<P> >que; for(int i=0;i<320;i++)d[i]=INF; d[s]=0; que.push(P(0,s)); while(!que.empty()) { P p=que.top(); que.pop(); int v=p.second; if(d[v]<p.first)continue; for(int i=0;i<G[v].size();i++) { edge e=G[v][i]; int tmp=p.first,mod=e.open+e.close; int re=tmp%mod; if(re<e.open&&e.open-re>=e.cost) { if(d[e.to]>tmp+e.cost) { d[e.to]=tmp+e.cost; que.push(P(d[e.to],e.to)); } } else if(e.open>=e.cost) { if(d[e.to]>tmp+e.cost+mod-re) { d[e.to]=tmp+e.cost+mod-re; que.push(P(d[e.to],e.to)); } } } } } int main() { int test=1; while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF) { for(int i=0;i<m;i++) { int u,v,a,b,t1; scanf("%d%d%d%d%d",&u,&v,&a,&b,&t1); edge e; e.to=v; e.open=a; e.close=b; e.cost=t1; G[u].push_back(e); } dijkstra(); init(); printf("Case %d: %d\n",test++,d[t]); } return 0; }
CSU 1333: Funny Car Racing 最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。