HDU 4725 The Shortest Path in Nya Graph(最短路建边)题解
2024-10-19 08:43:32
题意:给你n个点,m条无向边,每个点都属于一个层,相邻层的任意点都能花费C到另一层任意点,问你1到n最小路径
思路:没理解题意,以为每一层一个点,题目给的是第i个点的层数编号。这道题的难点在于建边,如果用最朴素的相邻层所有点互相连接,那么可能有5*10^4连5*10^4,复杂度O(n^2)。这里我们用拆点(?大概),把每一层拆出一个点,作为每一层点和相邻层连接的中转站。这里要特别注意,同一层的点的距离不是0,所以我们建边不能全是无向边:
1.层与层无向边,权值C
2.层与同层点建单向边,权值0
2.点与相邻层单向边,权值C
这样,每个点都能通过每层拆出的点连接相邻层的点,而且同层的点的距离不为0。然而写完这些后我又TLE了...orz,把建边的vector邻接表改成手动建边,358ms过
代码:
#include<cstdio>
#include<set>
#include<cmath>
#include<stack>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = +;
const int INF = 0x3f3f3f3f;
struct Edge{
int v,w,next;
}edge[*maxn];
bool vis[maxn];
int dis[maxn],head[maxn],tot;
void spfa(int start){
memset(vis,false,sizeof(vis));
memset(dis,INF,sizeof(dis));
vis[start] = true;
dis[start] = ;
queue<int> q;
while(!q.empty()) q.pop();
q.push(start);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u];i != -;i = edge[i].next){
int v = edge[i].v;
int w = edge[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
q.push(v);
vis[v] = true;
}
}
}
}
}
void addEdge(int u,int v,int w){
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
int layer[maxn];
bool have[maxn];
int main(){
int T;
int n,m,C,Case = ;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&C);
tot = ;
memset(head,-,sizeof(head));
memset(have,false,sizeof(have));
for(int i = ;i <= n;i++){
scanf("%d",&layer[i]);
have[layer[i]] = true;
}
for(int i = ;i < n;i++){ //层层建边
if(have[i] && have[i + ]){
addEdge(n + i,n + i + ,C);
addEdge(n + i + ,n + i,C);
}
}
for(int i = ;i <= n;i++){ //层点建边 相邻层点建边
addEdge(n + layer[i],i,);
if(layer[i] > )
addEdge(i,n + layer[i] - ,C);
if(layer[i] < n)
addEdge(i,n + layer[i] + ,C);
}
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
spfa();
if(dis[n] == INF){
printf("Case #%d: -1\n",Case++);
}
else{
printf("Case #%d: %d\n",Case++,dis[n]);
}
}
return ;
}
最新文章
- 数据库日常维护-CheckList_02有关数据库备份检查
- Jquery ajax运用执行顺序有误怎么解决
- WCF初探-18:WCF数据协定之KnownType
- RabbitMQ 安装
- [moka同学笔记]Yii2.0验证码
- Oracle定时执行存储过程
- [SVN(ubuntu)] svn 文件状态标记含义
- Learing WCF Chapter1 Fundamental WCF Concepts
- 【bzoj2434】[Noi2011]阿狸的打字机
- Android ArrayAdapter MultiAutoCompleteTextView
- C++11 tuple
- 无法显示TabHost的setIndicator设置的图片的问题解决办法
- leetcode Merge K sorted Lists python
- WPF和Expression Blend开发实例:一个样式实现的数字输入框
- 返璞归真 asp.net mvc (10) - asp.net mvc 4.0 新特性之 Web API
- VB.NET版机房收费系统---报表
- MATLAB-离散系统的数字PID控制仿真
- 利用PIL创建验证码
- Mybatis配置问题解决Invalid bound statement (not found)
- Java 多线程(七) 线程间的通信——wait及notify方法
热门文章
- 【黑金原创教程】【Modelsim】Modelsim原创教程连载导读【连载完成,共六章】
- 【BZOJ2251】[2010Beijing Wc]外星联络 后缀数组
- linux下安装F-prot杀毒软件
- 【Android】 ImageView.ScaleType设置图解
- org.apache.log4j日志级别
- 170630、springboot编程之普通类中调用spring管理的bean对象
- 160226、js常用的验证
- js判断浏览器是否安装Flash插件,并提示安装或开启
- FZU 2105 Digits Count
- HDU 1103 Flo's Restaurant(模拟+优先队列)