#### HDU 1385 – Minimum Transport Cost [Flody+路径]

vjudge题目链接

cpp代码：

```#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024;
int n, d[maxn][maxn], b[maxn], path[maxn][maxn];

void Flody() {
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
path[i][j] = j;
for(int k = 1; k <= n; ++k) {
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= n; ++j) {
int t = d[i][k] +  d[k][j] + b[k];
if(t < d[i][j]) {
d[i][j] = t;
path[i][j] = path[i][k];
}
else if(t == d[i][j] && path[i][j] > path[i][k]) {
path[i][j] = path[i][k];
}
}
}
}
}

int main()
{
while(cin >> n, n) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
cin >> d[i][j];
if(d[i][j] == -1)
d[i][j] = 99999999;
}
}
for(int i = 1; i <= n; ++i)
cin >> b[i];
Flody();
int u, v;
while(cin >> u >> v) {
if(u == -1 && v == -1) break;
int cost = d[u][v];
printf("From %d to %d :\n", u, v);
printf("Path: %d", u);
while(u != v) {
printf("-->%d", path[u][v]);
u = path[u][v];
}
printf("\nTotal cost : %d\n\n", cost);
}
}
return 0;
}

```