首页 > 代码库 > hiho一下 第二十五周（SPFA）
hiho一下 第二十五周（SPFA）
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
万圣节的晚上，小Hi和小Ho在吃过晚饭之后，来到了一个巨大的鬼屋！
鬼屋中一共有N个地点，分别编号为1..N，这N个地点之间互相有一些道路连通，两个地点之间可能有多条道路连通，但是并不存在一条两端都是同一个地点的道路。
不过这个鬼屋虽然很大，但是其中的道路并不算多，所以小Hi还是希望能够知道从入口到出口的最短距离是多少？
提示：Super Programming Festival Algorithm。输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为4个整数N、M、S、T，分别表示鬼屋中地点的个数和道路的条数，入口（也是一个地点）的编号，出口（同样也是一个地点）的编号。
接下来的M行，每行描述一条道路：其中的第i行为三个整数u_i, v_i, length_i，表明在编号为u_i的地点和编号为v_i的地点之间有一条长度为length_i的道路。
对于100%的数据，满足N<=10^5，M<=10^6, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。
对于100%的数据，满足小Hi和小Ho总是有办法从入口通过地图上标注出来的道路到达出口。
输出
对于每组测试数据，输出一个整数Ans，表示那么小Hi和小Ho为了走出鬼屋至少要走的路程。
- 样例输入
5 10 3 51 2 9972 3 5053 4 1184 5 543 5 4803 4 7965 2 7942 5 1465 4 6042 5 63
- 样例输出
172
代码君1 #include <iostream> 2 #include <cstdio> 3 #include <memory.h> 4 #include <string> 5 #include <vector> 6 #include <queue> 7 #include <set> 8 #include <map> 9 #include <algorithm>10 #include <climits>11 using namespace std;12 13 #define MAXN 11111114 #define MAX 111111115 struct node {16 int x,weight;17 };18 vector< node > mp[MAXN];19 int cost[MAX]; //存储到起始点的最近距离20 int n,m,s,e;21 22 bool spfa()23 {24 queue<node> q;25 cost[s] = 0;26 q.push({s,0});27 while (!q.empty())28 {29 node now = q.front();30 q.pop();31 if (cost[now.x] < now.weight) continue;32 else cost[now.x] = now.weight;33 for (int i = 0;i < mp[now.x].size();i++) {34 //如果未访问过或者距离可更新35 if (cost[mp[now.x][i].x] == -1 || cost[mp[now.x][i].x] > mp[now.x][i].weight + cost[now.x]) {36 cost[mp[now.x][i].x] = mp[now.x][i].weight + cost[now.x]; 37 q.push({mp[now.x][i].x,cost[mp[now.x][i].x]});38 }39 40 }41 }42 return true;43 }44 45 int main()46 {47 int a,b,w;48 memset(cost,-1,sizeof(cost)); //权值为-1表示还未访问过49 cin >> n >> m >> s >> e;50 for (int i = 0;i < m; ++ i) {51 cin >> a >> b >> w;52 mp[a].push_back({b,w});53 mp[b].push_back({a,w});54 }55 if (spfa())56 cout << cost[e] << endl;57 return 0;58 }
另外附上大牛的SFPA代码
SPFA的两种写法，bfs和dfs，bfs判别负环不稳定，相当于限深度搜索，但是设置得好的话还是没问题的，dfs的话判断负环很快
BFS1 int spfa_bfs(int s) 2 { 3 queue <int> q; 4 memset(d,0x3f,sizeof(d)); 5 d[s]=0; 6 memset(c,0,sizeof(c)); 7 memset(vis,0,sizeof(vis)); 8 9 q.push(s); vis[s]=1; c[s]=1;10 //顶点入队vis要做标记，另外要统计顶点的入队次数11 int OK=1;12 while(!q.empty())13 {14 int x;15 x=q.front(); q.pop(); vis[x]=0;16 //队头元素出队，并且消除标记17 for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表18 {19 int y=v[k];20 if( d[x]+w[k] < d[y])21 {22 d[y]=d[x]+w[k]; //松弛23 if(!vis[y]) //顶点y不在队内24 {25 vis[y]=1; //标记26 c[y]++; //统计次数27 q.push(y); //入队28 if(c[y]>NN) //超过入队次数上限，说明有负环29 return OK=0;30 }31 }32 }33 }34 35 return OK;36 37 }
DFS1 int spfa_dfs(int u) 2 { 3 vis[u]=1; 4 for(int k=f[u]; k!=0; k=e[k].next) 5 { 6 int v=e[k].v,w=e[k].w; 7 if( d[u]+w < d[v] ) 8 { 9 d[v]=d[u]+w;10 if(!vis[v])11 {12 if(spfa_dfs(v))13 return 1;14 }15 else16 return 1;17 }18 }19 vis[u]=0;20 return 0;21 }
hiho一下 第二十五周（SPFA）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。