ZOJ 1456 Minimum Transport Cost(floyd+后继路径记录)
2024-10-15 15:11:04
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1456
题意:
求最短路并且输出字典序最小的答案。
思路:
如果用dijkstra来做的话,会比较麻烦,这里直接用floyd会简单的多,只需要记录好后继路径即可。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = + ; int n, m; int val[maxn];
int mp[maxn][maxn];
int path[maxn][maxn]; void floyd()
{
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(mp[i][k]==INF || mp[k][j]==INF) continue;
int sum=mp[i][k]+mp[k][j]+val[k];
if(mp[i][j]>sum)
{
mp[i][j]=sum;
path[i][j]=path[i][k];
}
else if(mp[i][j]==sum && path[i][j]>path[i][k])
path[i][j]=path[i][k];
}
}
}
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d",&n) && n)
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
scanf("%d",&mp[i][j]);
if(mp[i][j]==-) mp[i][j]=INF;
path[i][j]=j; //i的后继路径为j
}
for(int i=;i<=n;i++) scanf("%d",&val[i]);
floyd(); while(true)
{
int s,t;
scanf("%d%d",&s,&t);
if(s==- && t==-) break;
printf("From %d to %d :\n",s,t);
printf("Path: %d",s);
int tmp=s;
while(tmp!=t)
{
printf("-->%d",path[tmp][t]);
tmp=path[tmp][t];
}
printf("\n");
printf("Total cost : %d\n\n",mp[s][t]);
}
}
return ;
}
最新文章
- 关于Python3爬虫抓取网页Unicode
- 使用Ant部署应用程序系统
- 【HDU】1848 Fibonacci again and again
- shell exit 0 exit 1
- 关于java设计模式与极品飞车游戏的思考
- A Full Hardware Guide to Deep Learning
- WEB性能测试:你应该带上VisualStudio2010
- php中Maximum execution time of 120 seconds exceeded时间超时错误解决方案
- xbox360版本之分
- oracle_根据表名拼装语句
- C# 单例模式(Singleton Pattern)
- 1.shell学习之常用语句
- php 慢配置文件
- LeetCode--023--合并K个排序链表
- Android Bitmap操作问题之Canvas: trying to use a recycled bitmap
- BTrace使用简介
- CSS3实现基本图形
- day 67 django 之ORM 增删改查基础
- python之numpy.power()数组元素求n次方
- ARM Cortex-A9 (tiny 4412)