水題,但是g++超時,c++對了 不解
#include<stdio.h> const int MAXN= 505 ; const int INF= 0x7fffffff ; int xx[MAXN]; int pre[MAXN]; int map[MAXN][MAXN]; int dist[MAXN]; int ans,n,flag; void Prim() { int i,j,k; int mn; bool p[MAXN]; for (i= 2 ;i<=n;i++ ) { p[i] = false ; pre[i] = 1 ; dist[i] =map[ 1 ][i]; } dist[ 1 ]= 0 ; p[ 1 ]= true ; for (i= 1 ;i<=n- 1 ;i++ ) { mn = INF; k = 0 ; for (j= 1 ;j<=n;j++ ) { if (!p[j] && dist[j]< mn) { mn = dist[j]; k = j; } } if (k== 0 ) {flag= 1 ; return ;} p[k] = true ; ans += dist[k]; for (j= 1 ;j<=n;j++ ) { if (!p[j] && map[k][j]!=INF && dist[j]> map[k][j]) { dist[j] = map[k][j]; pre[j] = k; } } } } int main() { int T; int m,k,t,i,j,a,b,c; int xx[MAXN]; scanf( " %d " ,& T); while (T-- ) { scanf( " %d%d%d " ,&n,&m,& k); { for (i= 1 ;i<=n;i++ ) { for (j= 1 ;j<=n;j++ ) { if (i==j) map[i][j]= 0 ; else map[i][j]= INF; } } for (i= 0 ;i<m;i++ ) { scanf( " %d%d%d " ,&a,&b,& c); if (map[a][b]>c) map[a][b]=map[b][a]= c; } for (i= 0 ;i<k;i++ ) { scanf( " %d " ,& t); for (j= 0 ;j<t;j++ ) scanf( " %d " ,& xx[j]); for (j= 1 ;j<t;j++ ) { map[xx[j]][xx[j - 1 ]]=map[xx[j- 1 ]][xx[j]]= 0 ; } } ans =flag= 0 ; Prim(); if (flag) printf( " -1\n " ); else printf( " %d\n " ,ans); } } return 0 ; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
