poj 3268 Silver Cow Party(单源最短路径Dijkstra·最小环)

2024-03-27 23:32

本文主要是介绍poj 3268 Silver Cow Party(单源最短路径Dijkstra·最小环),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11757

Silver Cow Party
Time Limit: 2000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u

Submit Status

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively:  NM, and  X
Lines 2..  M+1: Line  i+1 describes road  i with three space-separated integers:  AiBi, and  Ti. The described road runs from farm  Ai to farm  Bi, requiring  Ti time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output

10

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.
终点给出,是一个定点。所有的牛犊都会到达该点并且由通过不同的道路回到原点。由此想到单源最短路径,把终点看作源点S,但是怎么回去呢?看了一个大神的博客,矩阵转置(第一次自己转置都写错了||-_-)。效果:(1,2) (2,7) (7,4)  --> (2,1) (7,2) (4,7) means (4,7) (7,2) (2,1)  起点和终点的地位互换!这样再一次用Dijkstra或者spfa等算法求出回家的最短路径就构成了环路。
关于矩阵转置举个例子:
for(int i=0;i<4;i++){
         for(int j=0;j<=i;j++){
             swap(a.m[i][j],a.m[j][i]);
         }
}
不是:
for(int i=0;i<4;i++){
         for(int j=0;j<4;j++){
             swap(a.m[i][j],a.m[j][i]);
         }
}
来看看效果:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct matrie{int m[4][4];
};
matrie a={
1,2,3,4,
7,3,5,5,
6,6,6,6,
0,0,0,0
};
void show(){cout<<"show: \n";for(int i=0;i<4;i++){for(int j=0;j<4;j++){cout<<a.m[i][j]<<" ";}cout<<endl;}
}
void trans(){for(int i=0;i<4;i++){for(int j=0;j<=i;j++){swap(a.m[i][j],a.m[j][i]);cout<<i<<" "<<j<<": "<<endl;show();}}
}int main()
{trans();return 0;
}
0 0: 
show: 
1 2 3 4 
7 3 5 5 
6 6 6 6 
0 0 0 0 
1 0: 
show: 
1 7 3 4 
2 3 5 5 
6 6 6 6 
0 0 0 0 
1 1: 
show: 
1 7 3 4 
2 3 5 5 
6 6 6 6 
0 0 0 0 
2 0: 
show: 
1 7 6 4 
2 3 5 5 
3 6 6 6 
0 0 0 0 
2 1: 
show: 
1 7 6 4 
2 3 6 5 
3 5 6 6 
0 0 0 0 
2 2: 
show: 
1 7 6 4 
2 3 6 5 
3 5 6 6 
0 0 0 0 
3 0: 
show: 
1 7 6 0 
2 3 6 5 
3 5 6 6 
4 0 0 0 
3 1: 
show: 
1 7 6 0 
2 3 6 0 
3 5 6 6 
4 5 0 0 
3 2: 
show: 
1 7 6 0 
2 3 6 0 
3 5 6 0 
4 5 6 0 
3 3: 
show: 
1 7 6 0 
2 3 6 0 
3 5 6 0 
4 5 6 0 
是的,就是这样。
Dijkstra:基于贪心的思想。不足之处在于不能有负边,用于求解单源最短路径问题。这里没有负边问题,所以我就用它吧。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1005,INF=0x3f3f3f3f;
int dis1[maxn],dis2[maxn],map[maxn][maxn],pre[maxn];
int n,m,s;
bool p[maxn];
void Dijkstra(int dis[]){memset(p,0,sizeof(p));for(int i=1;i<=n;i++){if(i!=s){ dis[i]=map[s][i]; pre[i]=s; }else pre[i]=0;}dis[s]=0;p[s]=1;for(int i=1;i<n;i++){  //循环n-1次,求s到其他n-1个点的最短距离int minm=INF,k=0;for(int j=1;j<=n;j++){ //寻找最近的点if(p[j]==0&&dis[j]<minm){minm=dis[j];k=j;}}if(k==0) return;  //没有可以拓展的点p[k]=1;for(int j=1;j<=n;j++){  if(p[j]==0&&map[k][j]!=INF&&dis[j]>dis[k]+map[k][j]){ //利用最近的点更新其他点的距离dis[j]=dis[k]+map[k][j];pre[j]=k;}}}
}
void trans(){for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){swap(map[i][j],map[j][i]);}}
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>n>>m>>s){int a,b,c;memset(map,0x3f,sizeof(map));for(int i=1;i<=n;i++) map[i][i]=0;while(m--){scanf("%d%d%d",&a,&b,&c);if(a!=b&&map[a][b]>c)map[a][b]=c;}Dijkstra(dis1);trans();Dijkstra(dis2);int ans=0;for(int i=1;i<=n;i++){if(i!=s)ans=max(ans,dis1[i]+dis2[i]);}printf("%d\n",ans);}return 0;
}


这篇关于poj 3268 Silver Cow Party(单源最短路径Dijkstra·最小环)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/853768

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M