数据结构求最短路径及其花费代码,C代码库,德仔网

代码语言

代码分类

【C】数据结构求最短路径及其花费

作者:xgreatboy / 发布于2014/6/17/ 769


	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	#define inf 10000000
	const int Maxn = 200005;
	int N,M;
	struct Edge{
	 int v,next;
	 int dt,ct;
	}edge[Maxn];
	int first[1005];
	int r,s,t;
	int vis[1005];
	struct BNode{
	 int dist,cost;
	}P[1005];
	void addedge(int u, int v, int d, int p)
	{
	 edge[r].next = first[u];
	 edge[r].v = v;
	 edge[r].dt = d;
	 edge[r].ct = p;
	 first[u] = r;
	 r++;
	}

	int findminode()
	{
	 int i,Maxn = inf;
	 int index = 0;
	 for(i = 1; i<=N; i++)
	 if(P[i].dist<Maxn && !vis[i])
	 {
	 Maxn = P[i].dist;
	 index = i;
	 }
	 if(index)
	 {
	 for(i = 1; i<=N; i++)
	 if(P[i].cost<P[index].cost && !vis[i])index = i;
	 }
	 return index;
	}

	void solve()
	{
	 int i;
	 for(i = 1; i<=N; i++)
	 P[i].dist = P[i].cost = inf;
	 P[s].dist = P[s].cost = 0;
	 memset(vis,0,sizeof(vis));
	 int index = 1;
	 while(index<N)
	 {
	 int x = findminode();
	 if(!x)break;
	 vis[x] = 1; index++;
	 for(i = first[x]; i!=-1; i = edge[i].next)
	 {
	 int v = edge[i].v;
	 if(P[x].dist+edge[i].dt<P[v].dist && !vis[v])
	 {
	 P[v].dist = P[x].dist+edge[i].dt;
	 P[v].cost = P[x].cost+edge[i].ct;
	 }
	 else if(P[x].dist+edge[i].dt == P[v].dist && !vis[v])
	 {
	 if(P[x].cost+edge[i].ct<P[v].cost)P[v].cost = P[x].cost+edge[i].ct;
	 }
	 }
	 }
	 cout<<P[t].dist<<' '<<P[t].cost<<endl;
	}

	int main()
	{
	 int i,u,v,d,p;
	 while(scanf("%d%d",&N,&M)!=EOF)
	 {
	 if(N == 0 && M == 0)break;
	 memset(first,-1,sizeof(first));
	 r = 0;
	 for(i = 0; i<M; i++)
	 {
	 scanf("%d%d%d%d",&u,&v,&d,&p);
	 addedge(u,v,d,p);
	 addedge(v,u,d,p);
	 }
	 scanf("%d%d",&s,&t);
	 solve();
	 }
	 return 0;
	}

试试其它关键字

　数据结构　　　　最短路径　

同语言下

可能有用的

xgreatboy贡献的其它代码(2)