UVA12661 有趣的赛车比赛

Posted by Cww97 on 2016-10-04

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52735264
白书上的例题,n个点m条单向边,每条边周期性开放和关闭,时间分别为a,b
求s到t的最短路

首先对于a>cost的边,可以直接删掉
spfa,算dist的时候,加入等待的时间
然后,就没有然后了

写代码越来越模块化(chou)了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100007;
const int INF=0x3f3f3f3f;
struct SPFA{
struct Edge{
int from,to,cost,a,b;
Edge(){}
Edge(int x,int y,int z,int a,int b):
from(x),to(y),cost(z),a(a),b(b){}
bool canPass(){return a>=cost;}//题目里的
void read(){scanf("%d%d%d%d%d",&from,&to,&a,&b,&cost);}
};
int n, m;
vector <Edge> edges;
vector <int > G[N];

inline void AddEdge(){
Edge e; e.read();
if (!e.canPass())return ;
edges.push_back(e);
int top = edges.size();
G[e.from].push_back(top-1);
}

inline void Init(int n,int m){
this -> n = n; this -> m = m;
edges.clear();
for (int i=0;i<=n;i++)G[i].clear();
for (int i=1;i<=m;i++) AddEdge();
}

bool inq[N];
int d[N],cnt[N];
inline int spfa(int s,int t){
queue<int> Q;
memset(inq, 0, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
memset( d ,INF,sizeof( d ));
d[s] = 0;inq[s]=1;Q.push(s);
for (;!Q.empty();){
int u = Q.front();Q.pop();
inq[u]= 0;
for (int i=0;i<G[u].size();i++){
Edge &e = edges[G[u][i]];
int val = d[u],s = d[u] ;//
val %= (e.a + e.b);//特殊题目
if (val>e.a) s+=e.b-(val-e.a);//
else if (e.a<val+e.cost)s+=e.a+e.b-val;//
if (d[u]<INF&&s+e.cost<d[e.to]){
d[e.to] = s + e.cost;
if (!inq[e.to]){
Q.push(e.to);inq[e.to] = 1;
if (++cnt[e.to]>n)return INF;
}
}
}
}
return d[t];
}
}g;

int main(){
//freopen("in.txt","r",stdin);
int n,m,s,t;
for (int T=0;~scanf("%d%d%d%d",&n,&m,&s,&t);){
g.Init(n,m,s,t);
int ans = g.spfa(s,t);
printf("Case %d: %d\n",++T,ans);
}
return 0;
}

这波图论挂vjudge上了
http://vjudge.net/contest/107921#overview
密码cww