題目連結: https://tioj.ck.tp.edu.tw/problems/1096
# 內容
給你 N 個捷運站以及連結他站的時間，求花費最短的環狀路線所花的時間，就是求最小環的意思
# 思路
運用 floyd-warshall，就可以求出到達自己點 (從自己點) 的最短距離啦！！
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
#define INF 9999999 | |
int graph[101][101]; | |
int main(){ | |
int n; cin>>n; | |
while(n!=0){ | |
for(int i=0;i<n;i++){ | |
for(int j=0;j<n;j++){ | |
cin>>graph[i][j]; | |
if(graph[i][j]==0) graph[i][j]=INF; | |
} | |
} | |
for(int k=0;k<n;k++) | |
for(int i=0;i<n;i++) | |
for(int j=0;j<n;j++) | |
if(graph[i][k]+graph[k][j] < graph[i][j]) | |
graph[i][j] =graph[i][k]+graph[k][j]; | |
int minn=INF; | |
for(int i=0;i<n;i++) | |
if(graph[i][i]<minn) | |
minn=graph[i][i]; | |
if(minn==INF) | |
puts("-1"); | |
else | |
cout<<minn<<endl; | |
cin>>n; | |
} | |
return 0; | |
} |
