AC日记——最短路 洛谷 P2384
2024-10-04 12:49:43
题目背景
狗哥做烂了最短路,突然机智的考了Bosh一道,没想到把Bosh考住了...你能帮Bosh解决吗?
他会给你100000000000000000000000000000000000%10金币w
题目描述
给定n个点的带权有向图,求从1到n的路径中边权之积最小的简单路径。
输入输出格式
输入格式:
第一行读入两个整数n,m,表示共n个点m条边。 接下来m行,每行三个正整数x,y,z,表示点x到点y有一条边权为z的边。
输出格式:
输出仅包括一行,记为所求路径的边权之积,由于答案可能很大,因此狗哥仁慈地让你输出它模9987的余数即可。
废话当然是一个数了w
//谢fyszzhouzj指正w
对于20%的数据,n<=10。
对于100%的数据,n<=1000,m<=1000000。边权不超过10000。
输入输出样例
输入样例#1:
3 3
1 2 3
2 3 3
1 3 10
输出样例#1:
9
说明
好好看一看再写哟w
思路:
裸spfa;
来,上代码:
#include <cstdio>
#include <cstring>
#include <iostream> #define maxn 1005
#define maxm 1000005 using namespace std; struct EdgeType {
int v,e,w;
};
struct EdgeType edge[maxm<<]; int if_z,head[maxn],n,m,cnt;
int dis[maxn],que[maxm<<]; bool if_[maxn]; char Cget; inline void in(int &now)
{
now=,if_z=,Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} int main()
{
in(n),in(m);int u,v,w;
for(int i=;i<=m;i++)
{
in(u),in(v),in(w);
edge[++cnt].v=v,edge[cnt].w=w,edge[cnt].e=head[u],head[u]=cnt;
}
int h=,tail=;
for(int i=;i<=n;i++) dis[i]=0x7fffffff;
que[tail++]=,if_[]=true,dis[]=;
while(h<tail)
{
for(int i=head[que[h]];i;i=edge[i].e)
{
if(dis[edge[i].v]>dis[que[h]]*edge[i].w)
{
dis[edge[i].v]=dis[que[h]]*edge[i].w;
if(!if_[edge[i].v]) if_[edge[i].v]=true,que[tail++]=edge[i].v;
}
}
if_[que[h++]]=false;
}
cout<<dis[n]%;
return ;
}
最新文章
- struts2+hibernate整合-实现登录功能
- Cocos2d-x 3.2 学习笔记(十五)保卫萝卜 场景与数据
- js继承《转》
- poj2406 KMP
- 118. 119. Pascal&#39;s Triangle -- 杨辉三角形
- Codeforces Round #366 (Div. 2) C Thor(模拟+2种stl)
- 第一章 基本的SQL语句 (SQL基础)
- Python3 模块
- 使用LAMP创建基于wordpress的个从博客网站
- 个人笔记mysql游标
- POJ1743---Musical Theme(+后缀数组二分法)
- jquery插件autoComplete自动弹出
- PHP文件上传预览
- zf-表单填写以及相关业务流程
- java字符串以及字符类型基础
- IntelliJ IDEA及maven、git下载与配置
- Java复习题
- Rsync服务实战
- Nextday 参数化单元测试(测试用例)设计
- Mysql mysqld_safe启动与myslqd启动坑