POJ3255(Roadblocks)--次短路径
2024-08-26 19:07:49
3228K | 485MS | G++ | 2453B |
根据题意和测试用例知道这是一个求次短路径的题目。次短路径,就是比最短路径长那么一丢丢的路径,而题中又是要求从一点到指定点的次短路径,果断Dijkstra。
R (1 ≤ R ≤ 100,000,N (1 ≤ N ≤ 5000) ,length D (1 ≤ D ≤ 5000),所以我用链式向前星方法存储,这个不知道的点这里(我转载别人的,讲的挺详细)。
用一个二维数组dist[MAXN][2],去记录i->j的最短路径和次短路径,第二维是0表示当期拿记录最短边,是1表示当前记录次短边。思路是这样,dist初始值为INF,当if(!vis[j][0] && dis[j][0] < MIN),即找到最短边,标记下来;如果 else if(!vis[j][1] && dis[j][1] < MIN),则是次短边,标记下来。所后进行松弛操作。。。。
/*************************************************************************
> File Name: poj3255.cpp
> Author: YeGuoSheng
> Description:
给定n个点和需要到达的点编号
问从1号点到目标点的次短路径
> Created Time: 2019年07月21日 星期日 16时40分46秒
************************************************************************/ #include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<string>
#include<algorithm>
#include<iomanip>
#define INF 0x3f3f3f3f
#define MAXN 50010 struct node
{
int v;
int next;
int w;
}edges[MAXN<<]; int head[MAXN];
int cnt;
int dis[MAXN][];//dist [i][0]:1 最短路径 ,dist[i][1]次短路径
bool vis[MAXN][];//vis[i][0]:1 表示到结点i的最短路径已找到,vis[i][1]表示到结点i的次短路径已找到
int n,m; void add(int u,int v,int w)//链式向前星存储
{
edges[++cnt].v=v;
edges[cnt].w=w;
edges[cnt].next=head[u];
head[u]=cnt;
} void dijkstra(int s)
{
for(int i=;i <= n;i++)
{
dis[i][]=dis[i][]= INF;//dist [i][0] 最短路径 ,dist[i][1]次短路径
vis[i][]=vis[i][]= ;
}
dis[s][] = ;
for(int i = ;i < n*;i++)
{
int MIN = INF;
int k = ;
int flag = ;
for(int j = ;j <= n;j++)
{
if(!vis[j][] && dis[j][] < MIN)
{
MIN=dis[j][];//找到最小边 将点标记
k=j;
flag = ;
}
else if(!vis[j][] && dis[j][] < MIN)//否则找到的就是次短边
{
MIN=dis[j][];
k=j;
flag = ;
}
}
if(MIN == INF)break;//没找到 最短或次短路径
vis[k][flag]=;//标记到结点k的最小边或次短边已经找到
for(int j= head[k];j!=-;j=edges[j].next)
{
int v = edges[j].v;//第j条边的终点
int w = edges[j].w;//这条边的权重
if(MIN+w <= dis[v][])//小于最短边,更新最短边,同时最短边变为次短边
{
dis[v][] = dis[v][];//既然dis[v][0]有更小的,那么我先把原来的赋值给dis[v][1]
dis[v][] = MIN+w;
}
else if(MIN+w <= dis[v][])//如果大于最短边,小于次短边,根新次短边
{
dis[v][] = MIN+w;
}
}
}
}
int main()
{
memset(head,-,sizeof(head));
cnt = ;
scanf("%d%d",&n,&m);// n:目标结点, m:边的数幂
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dijkstra();
printf("%d\n",dis[n][]);
return ;
}
最新文章
- JSON.parse 与 eval() 对于解析json的问题
- WPF入门:XAML
- Database 'xxxx' is being recovered. Waiting until recovery is finished.
- MYSQL数据库导入数据时出现乱码的解决办法
- MySQL 如何修改字符集 utf8 改为 utf8mb4
- Cent OS yum 安装 Adobe flash player
- PHPExcel上传sae遇到: -1:fail to get xml content
- Android WebView JavaScript交互
- Css Div半透明
- django1.6.x(python3.3)使用pymysql连接mysql
- CSDN CODE平台,中国版Github简要使用说明
- Spring + qyartz+多任务实现任务调度功能。
- Python-uiautomator使用说明文档
- MVVM 简介
- python安装虚拟环境virtualenv
- Java中在特定区间产生随机数
- 关于Newtonsoft.Json,反序列化jason,内容有key的转换
- 求助!使用 ReportViewer 控件集成 Reporting Services2008 时,报";...401 unauthorized";错误!
- linux基础命令---du
- jQuery DataTables插件分页允许输入页码跳转
热门文章
- Jupyter Notebook in a virtual environment (virtualenv)
- Ionic4.x ion-refresher 下拉更新
- 算法习题---4-8特别困的学生(UVa12108)
- python设计模式第2版
- 编译Flink 1.9.0
- AD域策略启动关机脚本不执行的注意事项
- redis cluster环境搭建
- 【Leetcode_easy】933. Number of Recent Calls
- Find minimum number of people to reach to spread a message across all people in twitter
- SpringBoot学习笔记:Redis缓存