poj3268 Silver Cow Party(两次dijkstra)

时间:2022-09-21 18:38:19

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)的更多相关文章

  1. POJ-3268 Silver Cow Party---正向&plus;反向Dijkstra

    题目链接: https://vjudge.net/problem/POJ-3268 题目大意: 有编号为1-N的牛,它们之间存在一些单向的路径.给定一头牛的编号X,其他牛要去拜访它并且拜访完之后要返回 ...

  2. poj3268 Silver Cow Party(两次SPFA &vert;&vert; 两次Dijkstra)

    题目链接 http://poj.org/problem?id=3268 题意 有向图中有n个结点,编号1~n,输入终点编号x,求其他结点到x结点来回最短路长度的最大值. 思路 最短路问题,有1000个 ...

  3. POJ3268 Silver Cow Party&lpar;dijkstra&plus;矩阵转置)

    Silver Cow Party Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 15156   Accepted: 6843 ...

  4. POJ 3268 Silver Cow Party (双向dijkstra)

    题目链接:http://poj.org/problem?id=3268 Silver Cow Party Time Limit: 2000MS   Memory Limit: 65536K Total ...

  5. POJ3268 Silver Cow Party —— 最短路

    题目链接:http://poj.org/problem?id=3268 Silver Cow Party Time Limit: 2000MS   Memory Limit: 65536K Total ...

  6. poj 3268 Silver Cow Party&lpar;最短路dijkstra)

    描述: One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the bi ...

  7. POJ 3268 Silver Cow Party 最短路—dijkstra算法的优化。

    POJ 3268 Silver Cow Party Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbe ...

  8. POJ3268 Silver Cow Party Dijkstra最短路

    Description One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to atten ...

  9. 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 ...

随机推荐

  1. Jquery 小技巧

    [每个程序员都会的35个jQuery的小技巧]收集的35个jQuery的小技巧/代码片段,可以帮你快速开发

  2. jQuery文本段落展开和折叠效果

    <!DOCTYPE html> <head> <meta http-equiv="Content-Type" content="text/h ...

  3. 如何用iframe在网页中插入另一个网页的一部分内容,做成页中页

    <html><head></head><body><h1>这是一段引用的内容!!!</h1><div style=&quo ...

  4. 3&period;2 STL中的函数对象类模板

    *: STL中有一些函数对象类模板,如下所示: 1)例如要求两个double类型的x 和y 的积,可以: multiplies<double>()(x,y); 该表达式的值就是x*y的值. ...

  5. CDH版HDFS Block Balancer方法

    命令: sudo -u hdfs hdfs balancer 默认会检查每个datanode的磁盘使用情况,对磁盘使用超过整个集群10%的datanode移动block到其他datanode达到均衡作 ...

  6. 洛谷 &lbrack;P3258&rsqb; 松鼠的新家

    树上差分 对于一条路径 \(u->v\) 来说,设 \(t=LCA(u,v)\) ,d[]为差分数组 ,则有 d[u]++;d[v]++;d[t]--;d[fa[t]]--; 注意:题目中所给的 ...

  7. MS SQL自定义函数判断是否正整数

    可以写一个函数: 主要是使用正则来判断.另外输入字符是空的话,使用"-"来替换. CREATE FUNCTION [dbo].[svf_NonNegativeInteger] ( ...

  8. 【转】AJAX中JSON数据的返回处理问题

    AJAX处理复杂数据时,便会使用JSON格式.常用在对数据库的数据查询上.在数据库查询到数据后,便可在处理页面直接将数据转为JSON格式,然后返回. 本篇主要讨论:jQuery中,JSON数据在AJA ...

  9. ASP&period;NET Web API 启用跨域访问

    自定义特性 要在WebApi中实现JSONP,一种方式是实现自定义特性  http://*.com/questions/9421312/jsonp-with-asp-net-w ...

  10. 理解Scala - 核心规则

    看到这里有几个有意思的 规则,转载于此: Read Eval Print Loop (REPL) REPL在Scala里面指的是直接运行scala.exe进入的交互式命令行模式.广义上讲,也泛指那些在 ...