最短路

dijkstra

https://vjudge.net/contest/346398#problem/D

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define rep(i,x,y) if((x)<=(y)) for (register int i=(x);i<=(y);i++)
using namespace std;
int main()
{
	bool vis[200];
	int n,m,dis[200],a[200][200],t1,t2,t3,st;
	while (1)
	{
		cin>>n>>m;
		rep(i,1,n)
		  vis[i]=0;
		rep(i,1,n)
		  rep(j,1,n)
		    a[i][j]=999999;
		rep(i,1,n)
		{
		  dis[i]=999999;
		  vis[i]=0;
	    }
		if (n==0 and m==0)
		  return 0;
		rep(i,1,m)
		{
		  cin>>t1>>t2>>t3;
		  a[t1][t2]=t3;
		  a[t2][t1]=t3;
		}
		vis[1]=1;
		dis[1]=0;
		rep(i,1,n)
		{
			int minn=999999,temp=1;
			rep(j,1,n)
			  if (!vis[j] and dis[j]<minn)
			  {
			  	minn=dis[j];
			  	temp=j;
			  }
			vis[temp]=1;
			rep(j,1,n)
			  if (!vis[j] and dis[temp]+a[temp][j]<dis[j])
			    dis[j]=dis[temp]+a[temp][j];
		}
		cout<<dis[n]<<endl;
	}
	return 0;
}

最短路

原文：https://www.cnblogs.com/IamIron-Man/p/15236726.html