題目大意：開始時輸入n表示一個n*n的矩陣， 該矩陣表示從i到j要多少錢， 然後輸入經過每個城市時要的稅， 起點和終點不需要繳稅。要求輸出最小花費路徑， 並是字典順序。
Ps:法克， 輸出格式時比如1到1是 Path: 1， 而不是Path: 1-->1；就這個法克錯一下午啊！
code：dijkstar+字典路徑
#include <stdio.h>
#include <string.h>
#define inf 0x7fffffff
int n = 0, start = 0, end = 0, map[1002][1002], tax[1002], path[1002], used[1002], dis[1002];
int cmp(int a, int b, int c)
{
int cur = 0, path1[1002] = {0}, path2[1002] = {0}, count1 = 0, count2 = 0;
path1[count1++] = c, path2[count2++] = c;//path1與path2存的是到c點的路徑
for(cur = a; cur != -1; cur = path[cur])
path1[count1++] = cur;
for(cur = b; cur != -1; cur = path[cur])
path2[count2++] = cur;
count1--, count2--;
while(count1 != -1 || count2 != -1)
{
if(path1[count1]>path2[count2])
return b;
else if(path1[count1]<path2[count2])
return a;
count1--, count2--;
}
if(count1 == -1)
return a;
else
return b;
}
void dijkstar()
{
int i = 0, j = 0, k = 0, min = 0;
for(i = 1; i<=n; i++)
{
path[i] = -1;
used[i] = 0;
}
for(i = 1; i<=n; i++)
{
dis[i] = map[start][i];
}
used[start] = 1;
for(i = 0; i<n; i++)
{
min = inf;
for(j = 1; j<=n; j++)
if(!used[j] && min>dis[j] )
{
min = dis[j];
k = j;
}
used[k] = 1;
for(j = 1; j<=n; j++)
{
if(map[k][j] == inf) continue;
if(!used[j] && dis[j]>dis[k]+map[k][j]+tax[k])
{
dis[j] = dis[k]+map[k][j]+tax[k];
path[j] = k;
}
else if(!used[j] && dis[j]==dis[k]+map[k][j]+tax[k])//選取字典序小的
{
path[j] = cmp(path[j], k, j);//判斷j的前面是path[j]還是k
}
}
}
}
void print(int cur)
{
if(path[cur] != -1)
print(path[cur]);
printf("-->%d", cur);
}
int main()
{
int i = 0, j = 0;
while(scanf("%d",&n) , n)
{
for(i = 1; i<=n; i++)
for(j = 1; j<=n; j++)
{
scanf("%d",&map[i][j]);
if(map[i][j] == -1)
map[i][j] = inf;
}
for(i = 1; i<=n; i++)
scanf("%d",&tax[i]);
while(scanf("%d %d",&start, &end), start != -1 && end != -1)
{
dijkstar();
printf("From %d to %d :\nPath: %d", start, end, start);
if(start != end)
print(end);
printf("\n");
printf("Total cost : %d\n\n",dis[end]);
}
}
return 0;
}
code: floyd+字典路徑
path[i][j] 中存的是i到j路徑的第2個點， 比如1->2->3, path[1][3]存的是2， path[2][3] = 3;
#include <stdio.h>
#include <string.h>
#define inf 0x7fffffff
int n = 0, start = 0, end = 0, map[1002][1002], tax[1002], path[1002][1002];
void floyd()
{
int i = 0, j = 0, k = 0, item = 0;
for(i = 1; i<=n; i++)
for(j = 1; j<=n; j++)
path[i][j] = j;
for(k = 1; k<=n; k++)
for(i = 1; i<=n; i++)
{
if(i == k) continue;
for(j = 1; j<=n; j++)
{
if(map[i][k] == inf || map[k][j] == inf) continue;
item = map[i][k]+map[k][j]+tax[k];
if(map[i][j]>item)
{
map[i][j] = item;
path[i][j] = path[i][k];
}
else if(path[i][j]>path[i][k] && map[i][j]==item)
path[i][j] = path[i][k];
}
}
}
void print()
{
int cur = start;
printf("From %d to %d :\nPath: %d", start, end, start);
while(cur != end)
{
printf("-->%d",path[cur][end]);
cur = path[cur][end];
}
printf("\nTotal cost : %d\n\n", map[start][end]);
}
int main() www.2cto.com
{
int i = 0, j = 0;
while(scanf("%d",&n) , n)
{
for(i = 1; i<=n; i++)
{
for(j = 1; j<=n; j++)
{
scanf("%d",&map[i][j]);
if(map[i][j] == -1)
map[i][j] = inf;
}
}
for(i = 1; i<=n; i++)
scanf("%d",&tax[i]);
floyd();
while(scanf("%d %d",&start, &end), start != -1 && end != -1)
{
print();
}
}
return 0;
}
