POJ 2387 Til the Cows Come Home

传送门：http://poj.org/problem?id=2387

这是最短路径问题，本题有重边，但是spfa能解决这个问题：

实现代码：

SPFA:

1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxv=1005; 9 const int maxe=4005; 10 const int INF=1<<20; //刚这个开小了wrong了几次。 11 12 struct Edge{ 13 int v,w; 14 int next; 15 }; 16 17 int head[maxv]; 18 int dis[maxv],vis[maxv]; 19 Edge edges[maxe]; 20 21 int cnt=0; 22 void addEdge(int u,int v,int w){ 23 edges[cnt].v=v; 24 edges[cnt].w=w; 25 edges[cnt].next=head[u]; 26 head[u]=cnt++; 27 } 28 29 void spfa(int s,int n){ 30 for(int i=0;i<=n;i++){ 31 dis[i]=INF; 32 vis[i]=0; 33 } 34 35 dis[s]=0; 36 queue<int>q; 37 q.push(s); 38 vis[s]=1; 39 40 while(!q.empty()){ 41 int u=q.front(); 42 q.pop(); 43 44 for(int i=head[u];i!=-1;i=edges[i].next){ 45 int v=edges[i].v; 46 if(dis[v]>dis[u]+edges[i].w){ 47 dis[v]=dis[u]+edges[i].w; 48 49 if(!vis[v]){ 50 q.push(v); 51 vis[v]=1; 52 } 53 } 54 } 55 vis[u]=0; 56 } 57 58 } 59 60 int main(){ 61 int T,n; 62 scanf("%d%d",&T,&n); 63 memset(head,-1,sizeof(head)); 64 for(int i=0;i<T;i++){ 65 int u,v,w; 66 scanf("%d%d%d",&u,&v,&w); 67 addEdge(u,v,w); 68 addEdge(v,u,w); 69 } 70 spfa(n,n); 71 printf("%d\n",dis[1]); 72 return 0; 73 }

 Dijkstra实现：

#include <cstring> #include <cstdio> #include <algorithm> using namespace std;const int MAXN=10050; const int INF=1<<20; int map[MAXN][MAXN]; bool vis[MAXN]; int dis[MAXN],pre[MAXN] ;//路径//图的顶点坐标是从1开始的 //Dijkstra的邻接矩阵的实现 void Dijkstra(int st,int n){fill(dis,dis+n+1,INF);memset(vis,0,sizeof(vis));memset(pre,-1,sizeof(pre));dis[st]=0;for(int j=0;j<n;j++){int k=-1;int Min=INF;for(int i=1;i<=n;i++){if(!vis[i]&&Min>dis[i]){Min=dis[i];k=i;}}if(k==-1) break;vis[k]=true;for(int i=1;i<=n;i++)if(!vis[i]&&dis[i]>dis[k]+map[k][i]){dis[i]=dis[k]+map[k][i];pre[i]=k;}} }void output(int k){if(pre[k]==-1){return;}output(pre[k]);printf("%d ",pre[k]); }int main(){int T,N;scanf("%d%d",&T,&N);for(int i=1;i<=N;i++){fill(map[i],map[i]+N+1,INF);}for(int i=0;i<T;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);if(map[u][v]>w){map[u][v]=w;map[v][u]=w;}}Dijkstra(N,N);printf("%d\n",dis[1]);return 0; }

 

转载于:https://www.cnblogs.com/IKnowYou0/p/6477604.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的POJ 2387 Til the Cows Come Home的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。