soj3160: Clear And Present Danger
http://acm.scu.edu.cn/soj/problem.action?id=3160
简介题意：农夫John去找宝藏，按照藏宝图来说，他必须按照一个顺序到某些岛上才能找到，但是中间也可以去别的岛逛逛，每个岛之间海盗出没的概率给出，求出最小danger就好。
和我前几天写的基本一样啊，请参考http://blog.csdn.net/jing_laura/article/details/77653492
用Floyd，求出每两个点之间的最短路径（在此就是最小的危险系数），然后按照藏宝图的顺序，每个相加起来就行了。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f int map[110][110]; int sequence[10010]; void Floyd(int n) { for(int k = 1;k <= n; k++) for(int i = 1;i <= n; i++) for(int j = 1;j <= n; j++) if(map[i][j]>map[i][k]+map[k][j]) map[i][j] = map[i][k] + map[k][j]; } int main() { int N,M; while(~scanf("%d%d",&N,&M)) { memset(map,0,sizeof(map)); memset(sequence,0,sizeof(sequence)); for(int i = 1;i <= M; i++) scanf("%d",&sequence[i]); for(int i = 1;i <= N; i++) for(int j = 1;j <= N; j++) scanf("%d",&map[i][j]); Floyd(N); int sum = 0; for(int i = 1;i < M; i++) sum += map[sequence[i]][sequence[i+1]]; printf("%d\n",sum); } return 0; } 要注意的还是那三个for循环，顺序颠倒做无用功也没啥意义。