pku 2387 Til the Cows Come Home

it2022-05-06  33

用spfa做,额,到目前为止做的题目都几乎是模板题,三四道都是改一下输入就了事了,不过针对题目而已,还真有选择的余地,这里一个是我的,额,内存开得太大了,主要是1000*1000的矩阵来保存一个图的信息,本来很明显的得用邻接表来储存的,,而且只保存有用的边,而且加上用队列优化,快了不少呢

对比一下俩个代码吧

用邻接表的:

#include<cstdio> #include<iostream> using namespace std; #define N 4000 struct edge{ int v,next,cost; edge(int _v=0 ,int _next=0,int _cost=0):v(_v),next(_next),cost(_cost){}; }e[N]; int dist[N]; int n,m,p[N],tot = 0; void spfa(int s) { bool vist[N]; memset(vist,false ,sizeof(vist)); memset(dist,1,sizeof(dist)); dist[s] = 0; int que[N]; int begin,end; begin = end = 0; que[end++] = s; vist[s] = true; while(begin<end) { int t = que[begin++]; vist[t] = false; for(int j = p[t];j!=-1;j = e[j].next) { if(dist[e[j].v]>e[j].cost+dist[t]) { dist[e[j].v] = e[j].cost+dist[t]; if(!vist[e[j].v]) { vist[e[j].v] = true; que[end++] = e[j].v; } } } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { tot = 0; memset(p,-1,sizeof(p)); int a,b,c; for(int i = 0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); e[tot]=edge(b,p[a],c); p[a] = tot++; e[tot]=edge(a,p[b],c); p[b] = tot++; } spfa(1); printf("%d\n",dist[m]); } }

直接用邻接矩阵保存的:

#include<iostream> #define MAXINT 999999 using namespace std; int m,n; int dis[1001],Q[10010],vis[1001]; int map[1001][1001]; void SPFA(int n, int s) { // pri是队列头结点,end是队列尾结点 int i, pri, end, p; memset(vis, 0, sizeof(vis)); for(int i=0; i<10010; ++i) Q[i] = 0; for (i=1; i<=n; i++) dis[i] =MAXINT; dis[s] = 0; vis[s] = 1; Q[1] = s; pri = 1; end = 2; while (pri < end) { p = Q[pri]; for (i=1; i<=n; ++i) { //更新dis if (dis[p]+map[p][i] < dis[i]) { dis[i] = dis[p]+map[p][i]; if (!vis[i]) //未在队列中 { Q[end++] = i; vis[i] = 1; } } } vis[p] = 0; // 置出队的点为未标记 pri++; } } int main() { while(cin>>m>>n) { int a,b,len; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=MAXINT; for(int i=1;i<=m;i++) { cin>>a>>b>>len; if(map[a][b]>len) { map[a][b]=len; map[b][a]=len; } } SPFA(n,1); cout<<dis[n]<<endl; } return 0; }

转载于:https://www.cnblogs.com/nanke/archive/2011/08/13/2136868.html

相关资源:数据结构—成绩单生成器

最新回复(0)