洛谷——P3905 道路重建
2024-10-19 16:41:22
P3905 道路重建
题目描述
从前,在一个王国中,在n个城市间有m条道路连接,而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后,有d条道路被破坏了。国王想要修复国家的道路系统,现在有两个重要城市A和B之间的交通中断,国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使A与B之间的连接恢复,并要求修复的道路长度最小。
输入输出格式
输入格式:
输入文件road.in,第一行为一个整数n(2<n≤100),表示城市的个数。这些城市编号从1到n。第二行为一个整数m(n-1≤m≤n(n-1)/2),表示道路的数目。接下来的m行,每行3个整数i,j,k(1≤i,j≤n,i≠j,0<k≤100),表示城市i与j之间有一条长为k的道路相连。
接下来一行为一个整数d(1≤d≤m),表示战后被破坏的道路的数目。在接下来的d行中,每行两个整数i和j,表示城市i与j之间直接相连的道路被破坏。
最后一行为两个整数A和B,代表需要恢复交通的两个重要城市。
输出格式:
输出文件road.out,仅一个整数,表示恢复A与B间的交通需要修复的道路总长度的最小值。
输入输出样例
输入样例#1: 复制
3 2 1 2 1 2 3 2 1 1 2 1 3
输出样例#1: 复制
1
Floyd扩展
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 101 #define maxn 999999 using namespace std; bool vis[N][N]; int n,m,k,x,y,z,f[N][N]; int read() { ,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f; } int main() { n=read(),m=read(); ;i<=n;i++) ;j<=n;j++) f[i][j]=maxn*(i!=j); ;i<=m;i++) { x=read(),y=read(),z=read(); f[x][y]=f[y][x]=z; } k=read(); ;i<=k;i++) x=read(),y=read(),vis[x][y]=vis[y][x]=true; ;i<=n;i++) ;j<=n;j++) if(f[i][j]!=maxn) ; ;k<=n;k++) ;i<=n;i++) ;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); x=read(),y=read(); printf("%d",f[x][y]); ; }
最新文章
- PHP笔记(CSS篇)
- Nginx配置指定媒体类型文件强制下载
- const修饰的双重指针赋值解惑
- .net生成随机验证码图片
- C#基础(二)——C#中的构造函数
- Mac下搭建Eclipse Android开发环境
- AppCode3 常用 设置 及 快捷键 (持续更新)
- Js 获取当前月的天数
- 个人作业(2)---英语学习APP案例分析
- 为什么要学ADO.NET。。。什么是ADO.NET。。。
- 仿百度糯米TP5项目笔记
- 简单hdfs相关操作命令
- FineReport性能调优的一些办法
- LeetCode之旅(19)-Power of Two
- springdata 动态查询之分页
- 全局解释器锁GIL &; 线程锁
- Haskell语言学习笔记(19)File IO
- tortoisegit 右键无图标
- lrzsz的安装与配置
- oracle 28001错误 密码过期失效