首页 > 代码库 > [USACO08OPEN]寻宝之路Clear And Present Danger

[USACO08OPEN]寻宝之路Clear And Present Danger

OJ题号:洛谷2910

思路:Floyd

 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int main() { 5     int n,m; 6     scanf("%d%d",&n,&m); 7     int a[m]; 8     for(int i=0;i<m;i++) scanf("%d",&a[i]); 9     int d[n+1][n+1];10     for(int i=1;i<=n;i++) {11         for(int j=1;j<=n;j++) {12             scanf("%d",&d[i][j]);13         }14     }15     for(int k=1;k<=n;k++) {16         for(int i=1;i<=n;i++) {17             for(int j=1;j<=n;j++) {18                 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);19             }20         }21     }22     int ans=0;23     for(int i=1;i<m;i++) {24         ans+=d[a[i-1]][a[i]];25     }26     printf("%d\n",ans);27     return 0;28 }

 

[USACO08OPEN]寻宝之路Clear And Present Danger