https://vjudge.net/problem/HDU-2544

HDU - 2544 最短路 dijkstra+spfa

• • • 題目
    • 分析
    • AC代碼 spfa
    • AC代碼

題目

分析

模闆題

AC代碼 spfa

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=210,M=1e4+10;
int n,m,id;
int dis[N],bk[N];
int h[N],w[M],e[M],ne[M];
void add(int a,int b,int c)
{
	e[id]=b; w[id]=c;
	ne[id]=h[a];
	h[a]=id++;
}
void spfa()
{
	memset(bk,0,sizeof bk);
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	
	queue<int> q;
	q.push(1);
	bk[1]=1;
	
	while(q.size())
	{
		int t=q.front();
		q.pop();
		bk[t]=0;
		
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dis[j]>dis[t]+w[i])
			{
				dis[j]=dis[t]+w[i];
				if(!bk[j])
				{
					q.push(j);
					bk[j]=1;
				}
			}
		}
	}
 } 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	while(cin>>n>>m)
	{
		if(n==0 || m==0) break;
		memset(h,-1,sizeof h);
		int a,b,c;
		id=0;
		while(m--)
		{
			cin>>a>>b>>c;
			add(a,b,c);
			add(b,a,c);
		}
		spfa();
		cout<<dis[n]<<"\n";
	}
	return 0;
}
           

AC代碼

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
int n,m;
int g[N][N];
int dis[N],bk[N];
int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		if(n==0 || m==0) break;
		memset(g,0x3f,sizeof g);
		int a,b,c;
		while(m--)
		{
			scanf("%d %d %d",&a,&b,&c);
			if(g[a][b]>c)
				g[a][b]=c;
				
			if(g[b][a]>g[a][b])
				g[b][a]=g[a][b];
			else
				g[a][b]=g[b][a];
		}
		memset(dis,0x3f,sizeof dis);
		memset(bk,0,sizeof bk);
		dis[1]=0;
		for(int i=0;i<n-1;i++)
		{
			int t=-1;
			for(int j=1;j<=n;j++)
			{
				if(!bk[j] && (t==-1 || dis[t]>dis[j]))
					t=j;
			}
			bk[t]=1;
			for(int j=1;j<=n;j++)
				dis[j]=min(dis[j],dis[t]+g[t][j]);
		}
		cout<<dis[n]<<endl;
	}
	return 0;
}