hdu2066一个人的旅行(多源点多汇点的最短路径问题)
一个 路径 旅行 问题
2023-09-14 08:57:55 时间
思路:多源点,多会点的最短路径!
将最小号-1的节点但最源点,将最大号+1的点当作汇点!
将问题转变成从一个源点到一个汇点的最短路径的问题!
开始忘记初始化vector了,哇了好多次....坑爹啊
#include iostream
#include cstdio
#include algorithm
#include cstring
#include vector
#define M 1100
#define INF 0x3f3f3f3f
using namespace std;
struct node{
int v;
int tt;
node(){}
node(int v, int tt){
this-
this- tt=tt;
vector node v[M];
int d[M], vis[M];
int city[M];
int n;
int T, S, D;
void Dijkstra(){
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
d[0]=0;
vis[0]=1;
int root=0;
for(int j=0; j ++j){
int minLen=INF, p, len=v[root].size();
for(int i=0; i ++i){
int u=v[root][i].v;
if(!vis[u] d[u] d[root] + v[root][i].tt)
d[u] = d[root] + v[root][i].tt;
}//将所有的与root节点连接的节点的距离进行更新
for(int i=0; i =n+1; ++i)//然后从0节点到所有的节点的最短的距离!
if(!vis[i] minLen d[i]){
p=i;
minLen=d[i];
if(minLen==INF)
return;
root=p;
vis[root]=1;
int main(){
while(cin S T D){
int a, b, t;
n=-1;
while(S--){
cin a b t;
v[a].push_back(node(b, t));
v[b].push_back(node(a, t));
n=max(n, max(a,b));
while(T--){
cin a;
v[0].push_back(node(a, 0));
v[a].push_back(node(0, 0));
n=max(n,a);
for(int i=1; i ++i){
cin city[i];
n=max(n, city[i]);
for(int i=1; i ++i){
v[n+1].push_back(node(city[i],INF));
v[city[i]].push_back(node(n+1,0));
Dijkstra();
for(int i=0; i =n+1; ++i)
v[i].clear();
cout d[n+1] endl;
return 0;
}
相关文章
- 使用Vue写一个登录页面
- mips一个字是几个字节_计算机中字和字节的关系
- 有一个本地文件的路径或者文件的名字,计算文件的大小
- Media Query 在 CSS 中使用的一个具体例子
- AI色情被大平台驱逐后,这帮人搞了一个小社群,一心一意分享AI色情作品,精进技术
- 最安全Linux:最安全的发行版本是哪一个?(linux哪个发行版)
- 查询MySQL中的父节点:一个指南(mysql查询父节点)
- 如何在 MySQL 中创建一个 UTF8 编码的数据表?(mysql创建utf8表)
- Linux查看命令路径:一个轻松简单的方法。(linux查看命令路径)
- SQL Server样例库:一个强大的学习工具(sqlserver样例库)
- 数据库使用CMD编辑MySQL数据库一次学习一个新技能(cmd编辑mysql)
- 快速生成一个Redis队列(生成一个redis队列)
- 如何在MySQL中创建一个题库表(MySQL中创建题库表)
- MySQL为什么一个汉字占四个字节(mysql一个汉字占)
- Redis强大的NoSQL内存数据存储工具(写一个redis)
- Oracle中快速导出一个表的实现方法(oracle中导出一个表)
- 谷歌的Google Assistant会成为下一个Android吗?| CES 2019