http://acm.hdu.edu.cn/showproblem.php?pid=1385
题意: 找一个路径使得从一个地方坐的士到另一个地方花费最小，其中除了起点和终点，途中经过的站点要收费
Sample Input
5
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4
-1 -1
0
Sample Output
From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21
From 3 to 5 :
Path: 3-->4-->5
Total cost : 16
From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 999999999 //用0x3fffffff太大溢出，纠结了良久
#define M 205
int dist[M][M], n, b[M], path[M][M];
void floyd ()
{
int i, j, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
path[i][j] = j; //记录路径数组初始化，表示从i到j经过的第一个站
for (k = 1; k <= n; k++)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
int tp = dist[i][k] + dist[k][j] + b[k];
//溢出之地，因为+了b[k]，其实先判断是否有路会更保险
if (tp < dist[i][j])
dist[i][j] = tp, path[i][j] = path[i][k];
else if (tp == dist[i][j] && path[i][k] < path[i][j])
path[i][j] = path[i][k]; //按字典序记录路径
}
}
}
}
int main()
{
int i, j, u, v, tp;
while (scanf ("%d", &n), n)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf ("%d", dist[i]+j);
if (dist[i][j] == -1)
dist[i][j] = inf;
}
}
for (i = 1; i <= n; i++)
scanf ("%d", b+i);
floyd();
while (scanf ("%d%d", &u, &v), (u != -1 || v != -1))
{
printf ("From %d to %d :\n", u, v);
printf ("Path: %d", u);
tp = u;
while (u != v)
{
printf ("-->%d", path[u][v]);
u = path[u][v];
}
printf ("\nTotal cost : %d\n\n", dist[tp][v]);
}
}
return 0;
}
相关文章
