P2384 最短路
题目提供者Bosh
标签 图论 最短路 难度 普及/提高-
狗哥做烂了最短路，突然机智的考了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
说明
/*
直接spfa暴力.
数据很水.
如果边权值大一点就不能这样搞了.
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define mod 9987
#define MAXM 1000001
#define MAXN 1001
using namespace std;
int n,m,g[MAXN][MAXN],head[MAXN],cut,pre[MAXN],ans=1;
bool b[MAXN];
long long dis[MAXN];
struct data{int v,next,z;double x;}e[MAXM];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void add(int u,int v,int z)
{
e[++cut].v=v;
e[cut].x=log(z);
e[cut].z=z;
e[cut].next=head[u];
head[u]=cut;
}
void spfa()
{
memset(dis,127,sizeof dis);
queue<int>q;q.push(1);dis[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]*e[i].z)
{
dis[v]=dis[u]*e[i].z;
pre[v]=u;
if(!b[v]) b[v]=true,q.push(v);
}
}
}
}
int main()
{
int x,y,z;
n=read(),m=read();
for(int i=1;i<=m;i++)
{
x=read(),y=read(),z=read();g[x][y]=z;
add(x,y,z);
}
spfa();
printf("%d",dis[n]%mod);
return 0;
}/*
单源询问两点之间最小积路.
比较好的一种做法.
然后用log性质.
log(n*m)=log(n)+log(m)
然后我想最后取2的dis[n]次方作为ans.
但是因为double的缘故这个ans是错误的.
so我们在保证正确性的情况下记录路径求ans.
*/
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define mod 9987
#define MAXM 1000001
#define MAXN 1001
using namespace std;
int n,m,g[MAXN][MAXN],head[MAXN],cut,pre[MAXN],ans=1;
bool b[MAXN];
double dis[MAXN];
struct data{int v,next,z;double x;}e[MAXM];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void add(int u,int v,int z)
{
e[++cut].v=v;
e[cut].x=log(z);
e[cut].z=z;
e[cut].next=head[u];
head[u]=cut;
}
void spfa()
{
memset(dis,127,sizeof dis);
queue<int>q;q.push(1);dis[1]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].x)
{
dis[v]=dis[u]+e[i].x;
pre[v]=u;
if(!b[v]) b[v]=true,q.push(v);
}
}
}
}
int main()
{
int x,y,z;
n=read(),m=read();
for(int i=1;i<=m;i++)
{
x=read(),y=read(),z=read();g[x][y]=z;
add(x,y,z);
}
spfa();
x=n;
while(pre[x])
{
ans=(ans*g[pre[x]][x]%mod)%mod;
x=pre[x];
}
printf("%d",ans);
return 0;
}