https://vjudge.net/problem/POJ-3268
一开始floyd超时了。。
对正图定点求最短,对逆图定点求最短,得到任意点到定点的往返最短路。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define INF 0x3f3f3f3f
typedef unsigned long long ll;
using namespace std;
int t[][], rt[][];
int d[], rd[], vis[];
int n, m, x, a, b, T;
void dijkstra(int dist[], int a[][])
{
memset(vis, , sizeof(vis));
for(int i = ; i <= n; i++){
dist[i] = INF;
}
dist[x] = ;
for(int i = ; i <= n; i++){
int mini = INF, k = -;
for(int j = ; j <= n; j++){
if(!vis[j]&&mini > dist[j]){
mini = dist[j];
k = j;
}
}
vis[k] = ;
for(int j = ; j <= n; j++){
if(!vis[j]&&dist[j] > dist[k]+a[k][j]){
dist[j] = dist[k]+a[k][j];
}
}
}
}
int main()
{
cin >> n >> m >> x;
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++){
t[i][j] = INF; rt[i][j] = INF;
}
}
for(int i = ; i <= m; i++){
cin >> a >> b >> T;
t[a][b] = T;//图
rt[b][a] = T;//逆图
}
dijkstra(d, t);
dijkstra(rd, rt);
int maxm = -INF;
for(int i = ; i <= n; i++){
if(d[i]!=INF&&rd[i]!=INF&&d[i]+rd[i] > maxm){
maxm = d[i]+rd[i];
}
}
cout << maxm << endl;
return ;
}
poj3268 Silver Cow Party(两次dijkstra)的更多相关文章
-
POJ-3268 Silver Cow Party---正向+反向Dijkstra
题目链接: https://vjudge.net/problem/POJ-3268 题目大意: 有编号为1-N的牛,它们之间存在一些单向的路径.给定一头牛的编号X,其他牛要去拜访它并且拜访完之后要返回 ...
-
poj3268 Silver Cow Party(两次SPFA || 两次Dijkstra)
题目链接 http://poj.org/problem?id=3268 题意 有向图中有n个结点,编号1~n,输入终点编号x,求其他结点到x结点来回最短路长度的最大值. 思路 最短路问题,有1000个 ...
-
POJ3268 Silver Cow Party(dijkstra+矩阵转置)
Silver Cow Party Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 15156 Accepted: 6843 ...
-
POJ 3268 Silver Cow Party (双向dijkstra)
题目链接:http://poj.org/problem?id=3268 Silver Cow Party Time Limit: 2000MS Memory Limit: 65536K Total ...
-
POJ3268 Silver Cow Party —— 最短路
题目链接:http://poj.org/problem?id=3268 Silver Cow Party Time Limit: 2000MS Memory Limit: 65536K Total ...
-
poj 3268 Silver Cow Party(最短路dijkstra)
描述: One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the bi ...
-
POJ 3268 Silver Cow Party 最短路—dijkstra算法的优化。
POJ 3268 Silver Cow Party Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbe ...
-
POJ3268 Silver Cow Party Dijkstra最短路
Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to atten ...
-
POJ3268 Silver Cow Party (建反图跑两遍Dij)
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big co ...
随机推荐
-
Jquery 小技巧
[每个程序员都会的35个jQuery的小技巧]收集的35个jQuery的小技巧/代码片段,可以帮你快速开发
-
jQuery文本段落展开和折叠效果
<!DOCTYPE html> <head> <meta http-equiv="Content-Type" content="text/h ...
-
如何用iframe在网页中插入另一个网页的一部分内容,做成页中页
<html><head></head><body><h1>这是一段引用的内容!!!</h1><div style=&quo ...
-
3.2 STL中的函数对象类模板
*: STL中有一些函数对象类模板,如下所示: 1)例如要求两个double类型的x 和y 的积,可以: multiplies<double>()(x,y); 该表达式的值就是x*y的值. ...
-
CDH版HDFS Block Balancer方法
命令: sudo -u hdfs hdfs balancer 默认会检查每个datanode的磁盘使用情况,对磁盘使用超过整个集群10%的datanode移动block到其他datanode达到均衡作 ...
-
洛谷 [P3258] 松鼠的新家
树上差分 对于一条路径 \(u->v\) 来说,设 \(t=LCA(u,v)\) ,d[]为差分数组 ,则有 d[u]++;d[v]++;d[t]--;d[fa[t]]--; 注意:题目中所给的 ...
-
MS SQL自定义函数判断是否正整数
可以写一个函数: 主要是使用正则来判断.另外输入字符是空的话,使用"-"来替换. CREATE FUNCTION [dbo].[svf_NonNegativeInteger] ( ...
-
【转】AJAX中JSON数据的返回处理问题
AJAX处理复杂数据时,便会使用JSON格式.常用在对数据库的数据查询上.在数据库查询到数据后,便可在处理页面直接将数据转为JSON格式,然后返回. 本篇主要讨论:jQuery中,JSON数据在AJA ...
-
ASP.NET Web API 启用跨域访问
自定义特性 要在WebApi中实现JSONP,一种方式是实现自定义特性 http://*.com/questions/9421312/jsonp-with-asp-net-w ...
-
理解Scala - 核心规则
看到这里有几个有意思的 规则,转载于此: Read Eval Print Loop (REPL) REPL在Scala里面指的是直接运行scala.exe进入的交互式命令行模式.广义上讲,也泛指那些在 ...