| input | output |
|---|---|
0 2600 3800 2600 2500 2600 0 5300 3900 4400 3800 5300 0 1900 4500 2600 3900 1900 0 3700 2500 4400 4500 3700 0 |
13500 1 2 3 4 5 |
题意：有限制的最短路。
解析：虽然限制3号点不能第四个到达，但是顶点数固定是5个，这样其实就没必要用最短路算法了，直接预处理出最短路径的所有可能，然后选择最短的那条就行了。
AC代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int n = 5;
int a[6][6];
int act[][5] = {{1, 2, 3, 4, 5}, {1, 3, 2, 4, 5}, {1, 3, 4, 2, 5}, {1, 4, 3, 2, 5}}; //列举出所有符合条件的路径
int main(){
#ifdef sxk
freopen("in.txt", "r", stdin);
#endif //sxk
for(int i=1; i<=n; i++)
for(int j=1; j<=n ;j++) scanf("%d", &a[i][j]);
int foo = 0, ans = 123456789;
for(int i=0; i<4; i++){
int sum = 0;
for(int j=0; j<n-1; j++){
sum += a[ act[i][j] ][ act[i][j+1] ];
}
if(ans > sum){
ans = sum;
foo = i;
}
}
printf("%d\n", ans);
for(int i=0; i<n; i++) printf("%d%c", act[foo][i], i == n-1 ? '\n' : ' ');
return 0;
}
URAL 2005. Taxi for Programmers
原文：http://blog.csdn.net/u013446688/article/details/44535965