POJ3268 Silver Cow Party —— 最短路
题目链接:http://poj.org/problem?id=3268
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 24527 | Accepted: 11164 |
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
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
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
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define rep(i,a,n) for(int (i) = a; (i)<=(n); (i)++)
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 1e3+; int n, m, X;
int g[MAXN][MAXN]; int dis1[MAXN], dis2[MAXN];
bool vis[MAXN];
void dijkstra(int st, int dis[])
{
memset(vis, , sizeof(vis));
for(int i = ; i<=n; i++)
dis[i] = (i==st?:INF); for(int i = ; i<=n; i++)
{
int k, minn = INF;
for(int j = ; j<=n; j++)
if(!vis[j] && dis[j]<minn)
minn = dis[k=j]; vis[k] = ;
for(int j = ; j<=n; j++)
if(!vis[j] && g[k][j]!=INF)
dis[j] = min(dis[j], dis[k]+g[k][j]);
}
} int main()
{
while(scanf("%d%d%d", &n, &m, &X)!=EOF)
{
for(int i = ; i<=n; i++)
for(int j = ; j<=n; j++)
g[i][j] = INF;
for(int i = ; i<=m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u][v] = w;
}
dijkstra(X, dis1); //第一次跑最短路,计算X到各点的最短距离 for(int i = ; i<=n; i++) //将边取反
for(int j = i+; j<=n; j++)
swap(g[i][j], g[j][i]);
dijkstra(X, dis2); //第二次跑最短路,计算X到各点的距离,但因为边取反了,所以实际上是各点到X的最短距离。 int ans = ;
for(int i = ; i<=n; i++) //取两段距离之和的最大值
ans = max(ans, dis1[i]+dis2[i]);
printf("%d\n", ans);
}
}
最新文章
- Dom编程
- gcc-常见命令和错误
- linux web服务器必需的库文件
- Ajax中GET和POST的区别
- jQuery(一)delegate() 方法
- goldengate单向复制文档
- C++细节系列(零):零散记录
- 从零开始搭建口袋妖怪管理系统(2)-借助ngRoute实现详情页面跳转
- java开发环境配置——Maven
- Spark核心RDD、什么是RDD、RDD的属性、创建RDD、RDD的依赖以及缓存、
- Electron把网页打包成桌面应用并进行源码加密
- JavaScript 上万条数据 导出Excel文件(改装版)
- iOS 中 h5 页面 iframe 调用高度自扩展问题及解决
- File根据inputstream复制文件到临时目录,使用完之后删除
- 【mySQL】 - 主键
- 【LeetCode】81. Search in Rotated Sorted Array II (2 solutions)
- JavaScript 严格模式(use strict)
- Vue.js:自定义指令
- Monkey稳定性测试环境搭建说明
- ubuntu设置静态 ip
热门文章
- jenkins使用流程
- My97DatePicker 时间控件
- JS 操作XML
- Spring MVC集成Spring Data Reids和Spring Session实现Session共享
- http://www.cnblogs.com/shihaiming/
- Mysql 性能优化20个原则(1)
- BUPT复试专题—二叉排序树(2012)
- Android 使用ListView的A-Z字母排序功能实现联系人模块
- 搭建企业内部DNS服务器,docker 部署内部 dnsmasq
- 安卓自己定义View进阶-Canvas之绘制基本形状