bzoj2292【POJ Challenge 】永远挑战*
2024-10-09 10:14:57
题意:
有向图,每条边长度为1或2,求1到n最短路。点数≤100000,边数≤1000000。
题解:
有人说spfa会T,所以我用了dijkstra。不过这不是正解,神犇ZS告诉我正解应该是把所有边长度为2的边拆成两条,orz……
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define INF 0x3fffffff
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int n,m,d[maxn]; bool vis[maxn];
struct e{int t,w,n;}; e es[maxn*]; int ess,g[maxn];
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
struct hn{int u,w; bool operator <(const hn &a)const{return w>a.w;}}; priority_queue<hn>q;
int dijkstra(){
inc(i,,n)d[i]=INF; d[]=; q.push((hn){,});
while(!q.empty()){
int x=q.top().u; while(!q.empty()&&vis[x])q.pop(),x=q.top().u; if(q.empty()&&vis[x])break;
vis[x]=; for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){
d[es[i].t]=d[x]+es[i].w; q.push((hn){es[i].t,d[es[i].t]});
}
}
return d[n];
}
int main(){
n=read(); m=read(); inc(i,,m){int a=read(),b=read(),c=read(); pe(a,b,c);}
printf("%d",dijkstra()); return ;
}
20160905
最新文章
- Azure SQL Data Warehouse
- CGBitmapContextCreate函数参数详解
- SQL Server临界点游戏——为什么非聚集索引被忽略!
- js获取服务器控件DropDownList所选中的各项属性
- if条件判断语句的不同
- [Leetcode][Python]52: N-Queens II
- 提高duilib的richedit控制的一些特征
- .Net在线付款---Paydollar在线付款开发过程
- centos7 crontab笔记
- Mysql(集群)业务水平切割 垂直切割(Amoeba)
- 文本三剑客---gawk基础
- OpenSCAD 建模:矿泉水瓶花洒
- mysql中常用的函数
- 最大化及等比例测试演化Demo-Grid方法
- JB的IDE可视化MongoDB、MySQL数据库信息
- java多线程快速入门(一)
- tls 双向认证 client端代码例子
- == equals hashCode 总结比较
- V4L2驱动内核文档翻译(一)
- oracle 一对多数据分页查询筛选