https://www.luogu.com.cn/problem/P1359

https://www.luogu.com.cn/problem/P3385

题意：就是求最短路和判负环

存一下spfa 的模板…这样，两个有区别注意一下

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
//p1359租用游艇
const int INF=0x3f3f3f3f;
const int MAX=200+10;
int n,t,d[MAX];
struct Edge{
	int next,to,c;
}edge[MAX*MAX];
int tot,head[MAX];
void init(){
	tot=0;
	mem(head,-1);
}
void addedge(int u,int v,int c){
	edge[tot].to=v;
	edge[tot].c=c;
	edge[tot].next=head[u];
	head[u]=tot++;
}
bool spfa(int s){ 
	queue<int>q;
	bool inq[MAX];//队列中？
	for(int i=1;i<=n;i++) d[i] = INF;
	mem(inq,0);
	d[s]=0;
	q.push(s);
	while(!q.empty()){
		int u= q.front();
		q.pop();
		inq[u]=0;//清除在队列中标记 
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			int c=edge[i].c;
			if(d[v] > d[u] +c){
				d[v] = d[u] +c;
				if(!inq[v]){//已经在队列中，不要重复添加 
					inq[v]=1;
					q.push(v);
				}
			}
		}
	} 
	return true;
}
int main(){
	freopen("in","r",stdin);
	sf(n);
	init();
	fi(i,1,n)
		fi(j,i+1,n+1){
			sf(t);
			addedge(i,j,t);
		}
	spfa(1);
	pf(d[n]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//p3385【模板】负环
bool spfa(int s){
	queue<int>q;
	for(int i=1;i<=n;i++) d[i] = INF;
	mem(cnt,0);//进队次数 
	d[s]=0;
	cnt[s]=1;
	q.push(s);
	while(!q.empty()){
		int u= q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			int c=edge[i].c;
			if(d[v] > d[u] +c){
				d[v] = d[u] +c;
				q.push(v);
				if(++cnt[v]>n) return true;//某点入队n次，必存在负环 
			}
		}
	} 
	return false;
}