NC25005. [USACO 2008 Ope S]Clear And Present Danger
描述
输入描述
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 describes the ith island FJ must visit with a single integer: Ai
* Lines M+2..N+M+1: Line i+M+1 contains N space-separated integers that are the respective danger rating of the path between island i and islands 1, 2, ..., and N, respectively. The ith integer is always zero.
输出描述
* Line 1: The minimum danger that Farmer John can encounter while obtaining the treasure.
示例1
输入:
3 4 1 2 1 3 0 5 1 5 0 2 1 2 0
输出:
7
说明:
There are 3 islands and the treasure map requires Farmer John to visit a sequence of 4 islands in order: island 1, island 2, island 1 again, and finally island 3. The danger ratings of the paths are given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have danger ratings of 5, 2, and 1, respectively.C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 888K, 提交时间: 2023-04-24 12:40:47
#include<bits/stdc++.h>
#define N 1005
using namespace std;
int n,m,a[N*N],dis[N][N],ans;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>dis[i][j];
}
}
floyd();
for(int i=1;i<m;i++){
ans+=dis[a[i]][a[i+1]];
}
cout<<ans<<endl;
}
C++ 解法, 执行用时: 10ms, 内存消耗: 776K, 提交时间: 2022-02-03 21:44:08
#include<bits/stdc++.h>
using namespace std;
int a[10100],f[1100][1100];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>f[i][j];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
int ans=0;
a[0]=1;
for(int i=1;i<=m;i++)
ans+=f[a[i-1]][a[i]];
cout<<ans<<endl;
}