http://vijos.org/p/1046

求個最小環(huán)，Floyd即可。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ms(i,j) memset(i, j, sizeof(i)); using namespace std; int n,m; int G[102][102]; int dis[102][102]; int main () { while(scanf("%d%d", &n, &m)==2) {ms(G,27);for (int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d", &a,&b,&c);G[a][b]=G[b][a]=c; } memcpy(dis,G,sizeof(G));int ans = 10000000;for (int k=1;k<=n;k++){for (int i=1;i<=k-1;i++)for (int j=1;j<=k-1;j++)ans = min(ans, dis[i][j]+G[j][k]+G[k][i]);for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (k!=i&&k!=j&&i!=j)dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);}if (ans==10000000) printf("No solution.\n");else printf("%d\n", ans);}return 0; }

轉載于:https://www.cnblogs.com/flyinthesky1/p/6384336.html

總結

以上是生活随笔為你收集整理的|Vijos|图论最短路|P1046 观光旅游的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。