POJ3268 Silver Cow Party【最短路】
2024-10-02 11:12:32
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: N, M, and X
Lines 2.. M+1: Line i+1 describes road i with three space-separated integers: Ai,Bi, and Ti. The described road runs from farm Ai to farm Bi,
requiring Ti time units to traverse.
Lines 2.. M+1: Line i+1 describes road i with three space-separated integers: Ai,Bi, 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.
单向图 问牛去和回最短距离之和最大的
回来的好弄 直接最短路就行了
去时候的就把图反过来就行了
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>
#include<queue>
#include<stack>
#define inf 0x3f3f3f3f
using namespace std;
int n, m, x;
int graph[1005][1005];
bool vis[1005];
int dis1[1005], dis2[1005];
void dijkstra(int sec, int dis[])
{
memset(vis, false, sizeof(vis));
for(int i = 1; i <= n; i++){
dis[i] = graph[sec][i];
}
vis[sec] = true;
dis[sec] = 0;
for(int i = 1; i < n; i++){
int min = inf, min_num;
for(int j = 1; j <= n; j++){
if(!vis[j] && dis[j] < min){
min = dis[j];
min_num = j;
}
}
vis[min_num] = true;
for(int j = 1; j <= n; j++){
if(dis[j] > min + graph[min_num][j]){
dis[j] = min + graph[min_num][j];
}
}
}
}
int main()
{
while(cin>>n>>m>>x){
memset(graph, inf, sizeof(graph));
for(int i = 0; i < m; i++){
int f, t, w;
cin>>f>>t>>w;
graph[f][t] = w;
}
dijkstra(x, dis1);
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
swap(graph[i][j], graph[j][i]);
}
}
dijkstra(x, dis2);
int ans = -1;
for(int i = 1; i <= n; i++){
ans = max(ans, dis1[i] + dis2[i]);
}
cout<<ans<<endl;
}
return 0;
}
最新文章
- Lvs原理及部署之ARP协议
- WGS84坐标和UTM坐标的转换
- 基于bootstrap分页
- canvas-a10isPointPath2.html
- 抽屉显示控件SlidingDrawer入门
- Winform-CheckBox、ChecklistBox控件遍历代码
- JTree用法及JTree使用经验总结
- 编写isNull isArray isFunction的方法
- api的安全问题
- javamail邮件发送
- 利用 bat 批量处理命令实现手动控制mysql /Oracle 服务的开启和关闭
- Android打包遇到的那些坑
- FFmpeg源代码简单分析:avcodec_close()
- Android Gradle defaultConfig详解及实用技巧
- iOS: 并发编程的几个知识点
- Function,Object.creat();
- dp入门:最长不下降序列
- 制作macOS10.12系列的系统镜像文件
- 如何快速分析出现性能问题的Linux服务器
- python看内存