本文共 1338 字，大约阅读时间需要 4 分钟。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;#define MS(x,i) memset(x,i,sizeof(x))#define rep(i,s,e) for(int i=s; i<=e; i++)#define sc(a) scanf("%d",&a)#define scl(a) scanf("%lld",&a)#define sc2(a,b) scanf("%d %d", &a, &b)#define debug printf("debug......\n");#define pfd(x) printf("%d\n",x)#define pfl(x) printf("%lld\n",x)const double eps=1e-8;const double PI = acos(-1.0);const int inf = 0x3f3f3f3f;const ll INF = 0x7fffffff;const int maxn = 2e2+10;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0 , 0};int dis[maxn][maxn];int s,e;int x,y,w;int n,m;//起点可以从0 改为 1void Floyd(){ rep(k,0,n)//中继点从0到n开始枚举 rep(i,0,n)// 从i到j的距离更新 可以多经过中继点 rep(j,0,n) if(dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j];}int main(){ while(cin>>n>>m){ rep(i,0,n){ rep(j,0,n){ if(i==j) dis[i][j] = 0; else dis[i][j] = inf; } } rep(i,1,m){ cin>>x>>y>>w; if(dis[x][y] > w){ dis[x][y] = w; dis[y][x] = w; } } Floyd(); cin>>s>>e; if(dis[s][e] == inf) cout<<-1<
转载于:https://www.cnblogs.com/czsharecode/p/10715638.html