简单图论农场派对

ops/2024/11/28 15:18:56/

题目 2406: 

信息学奥赛一本通T1497-农场派对

时间限制: 2s 内存限制: 192MB 提交: 40 解决: 13

题目描述

原题来自:USACO 2007 Feb. Silver

N(1≤N≤1000) 头牛要去参加一场在编号为 x(1≤x≤N) 的牛的农场举行的派对。有 M(1≤M≤100000) 条有向道路,每条路长 Ti(1≤Ti≤100);每头牛都必须参加完派对后回到家,每头牛都会选择最短路径。求这 N 头牛的最短路径(一个来回)中最长的一条的长度。 特别提醒:可能有权值不同的重边。

输入格式

第 1 行:3 个空格分开的整数 N,M,X;

第 2…M 行:3 个空格分开的整数 Ai,Bi,Ti ,表示有一条从 Ai 到 Bi 的路,长度为 Ti 。

输出格式

一行一个数,表示最长最短路的长度。

样例输入

复制

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

样例输出

复制

10

 思路:

只需要考虑建立反向边图,将各点到x的最短路,转换为x点到各点的反向变图最短路。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int N = 1010, M = 100010;
int h1[N], h2[N], e1[M], e2[M], ne1[M], ne2[M], w1[M], w2[M], idx1, idx2;
bool st1[N], st2[N];
int dis1[N], dis2[N];
int n, m, x;
void add1(int a, int b, int c) {e1[idx1] = b, w1[idx1] = c, ne1[idx1] = h1[a], h1[a] = idx1++;
}
void add2(int a, int b, int c) {e2[idx2] = b, w2[idx2] = c, ne2[idx2] = h2[a], h2[a] = idx2++;
}
void dij(int x, int h[], bool st[], int dis[], int w[], int ne[], int idx,int e[]) {priority_queue<PII, vector<PII>, greater<PII>>q;q.push({ 0,x });dis[x] = 0;while (q.size()) {auto t = q.top();q.pop();int v = t.second;if (st[v]) {continue;}st[v] = true;for (int i = h[v]; ~i; i = ne[i]) {int j = e[i];if (st[j]) {continue;}if (dis[j] > dis[v] + w[i]) {dis[j] = dis[v] + w[i];q.push({ dis[j],j });}}}
}
void solve()
{cin >> n >> m >> x;memset(h1, -1, sizeof h1);memset(h2, -1, sizeof h2);memset(dis1, 0x3f, sizeof dis1);memset(dis2, 0x3f, sizeof dis2);for (int i = 1; i <= m; i++) {int a, b, c;cin >> a >> b >> c;add1(a, b, c);add2(b, a, c);}dij(x, h1, st1, dis1, w1, ne1, idx1,e1);dij(x, h2, st2, dis2, w2, ne2, idx2,e2);int ans = 0;for (int i = 1; i <= n; i++) {ans = max(ans, dis1[i] + dis2[i]);}cout << ans;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;//cin >> T;solve();return 0;
}


http://www.ppmy.cn/ops/137387.html

相关文章

C++笔记之单例模式与静态方法的使用辨析及代码规范

C++笔记之单例模式与静态方法的使用辨析及代码规范 code review! 文章目录 C++笔记之单例模式与静态方法的使用辨析及代码规范一.示例代码二.讲解2.1.代码规范2.1.1.单例模式实现2.1.2.静态方法实现2.1.3.单例模式结合静态方法2.2.总结一.示例代码 // 使用 set 方法设置值(通…

IT成长之路-ubuntu驱动篇

历时3天的蹂躏&#xff0c;总结驱动安装全面教程。 步骤一、安装gcc、g和make包 #脚本更新 sudo apt-get update #编译gcc sudo apt-get install gcc #编译g sudo apt-get install g #编译make sudo apt-get install make 注意&#xff1a; gcc、g版本可能会导致显卡驱动安…

离散化/C++ STL编码+set去重

先只做离散 #include<iostream> #include<algorithm> #include<vector> #include<set> using namespace std; int main() {int N 0;cin >> N;vector<int> old;set<int> ne;int temp;for (int i 0; i < N; i) {cin >> te…

基于STM32的智能无人机自主飞行与目标识别系统设计

目录 引言系统需求分析 2.1 功能需求 2.2 硬件需求 2.3 软件需求系统设计 3.1 总体架构 3.2 各模块设计系统实现 4.1 硬件实现 4.2 软件实现系统调试与优化总结与展望 1. 引言 随着无人机技术的快速发展&#xff0c;无人机在军事侦察、环境监测、物流配送等领域的应用逐渐增多…

搭建私有docker仓库

1. 安装docker依赖包 sudo yum install -y yum-utils device-mapper-persistent-data lvm2 sudo yum-config-manager --add-repo https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo sudo yum install docker-ce docker-ce-cli containerd.io sudo systemctl …

day29|leetcode 134. 加油站 , 135. 分发糖果 ,860.柠檬水找零 , 406.根据身高重建队列

8.加油站 在一条环路上有 n 个加油站&#xff0c;其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车&#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发&#xff0c;开始时油箱为空。 给定两个整数数组 gas 和…

【原创】springboot+vue高校勤工助学管理系统设计与实现

个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交给天意。 研究背景&#xff1a; 首…

实时数据开发 | Flink反压机制原因、影响及解决方案

今天是很忙碌的一天哦&#xff0c;有两个业务在催着验收&#xff0c;终于21&#xff1a;45卡点交上去了。 明早再修修补补一下应该就可以开始做实时方面的需求了&#xff0c;小紧张&#xff0c; 今天同事在同步会上讲这块业务的数据流时就提到了checkpoint和savepoint还有流处理…