题目描述
给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。
输入格式
第一行读入两个整数n，m，表示共n个点m条边。
接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。
输出格式
输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此输出它模9987的余数即可。
样例数据 1
备注
对于20%的数据，n<=10。
对于100%的数据，n<=1000，m<=1000000。边权不超过10000。
这题把最短路的dist改成乘起来的形式，然后还要取模，看起来裸的最短路会爆
实际上对边权取个log之后，dist就变成相加了
这样没法保证路径上取模的正确性，所以要先搞出最短路的路径然后再算出ans
我只能说这题卡spfa卡的不错……死都是90
就是不写dij你咬我啊
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 2147483647
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
#define md 100007
#define mod 9987
using namespace std;
struct edge{
int from,to,next,v;
double fv;
}e[800010],us[800010];
struct hashing{
int fr,to,next,rnk;
}hash[1000000];
int he[md];
int head[10010];
int n,m,cnt,cnt2,t,w,ans;
int q[100010];
double dist[100010];
int fa[100010];
int fav[100010];
bool mrk[100010];
inline int searc(int fr,int to)
{
int now=((fr+213)*(to+250))%md;
for (int i=he[now];i;i=hash[i].next)
if (hash[i].fr==fr&&hash[i].to==to)return hash[i].rnk;
return -1;
}
inline void ins_ha(int fr,int to,int rnk)
{
int now=((fr+213)*(to+250))%md;
hash[++cnt2].fr=fr;
hash[cnt2].to=to;
hash[cnt2].rnk=rnk;
hash[cnt2].next=he[now];
he[now]=cnt;
}
inline void ins_ed(int u,int v,int w)
{
us[++cnt].to=v;
us[cnt].from=u;
us[cnt].v=w;
us[cnt].next=head[u];
head[u]=cnt;
}
inline void ins_e(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].from=u;
e[cnt].v=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline LL read()
{
LL 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-'0';ch=getchar();}
return x*f;
}
inline void spfa(int S)
{
for (int i=1;i<=n;i++)mrk[i]=0;
for (int i=1;i<=n;i++)dist[i]=inf;
memset(q,0,sizeof(q));
q[0]=S;mrk[S]=1;dist[S]=0;
t=0;w=0;
do
{
int now=q[t];
t=(t+1)%md;
for (int i=head[now];i;i=e[i].next)
if (dist[e[i].to]>dist[now]+e[i].fv)
{
dist[e[i].to]=dist[now]+e[i].fv;
fa[e[i].to]=now;
fav[e[i].to]=e[i].v;
if (!mrk[e[i].to])
{
mrk[e[i].to]=1;
if (dist[q[t]]>dist[e[i].to])
{
t=(t-1+md)%md;
q[t]=e[i].to;
}
else
{
w=(w+1)%md;
q[w]=e[i].to;
}
}
}
mrk[now]=0;
}
while (t!=w);
}
int main()
{
n=read();m=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
int fnd=searc(x,y);
if (fnd==-1)
{
ins_ed(x,y,z);
ins_ha(x,y,cnt);
}else
{
us[fnd].v=min(us[fnd].v,z);
}
}
memset(head,0,sizeof(head));
int sum=cnt;cnt=0;
for (int i=1;i<=sum;i++)
{
ins_e(us[i].from,us[i].to,us[i].v);
}
for (int i=1;i<=cnt;i++)
e[i].fv=log(e[i].v);
spfa(1);
int s=n,ans=1;
while (s!=1)
{
ans=(ans*fav[s])%mod;
s=fa[s];
}
printf("%d\n",ans);
}