题目描述
给定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。
题解
一道很简单的最短路，取个对数并记录路径即可。
方案一：spfa+SLF优化，话说感觉spfa好写。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define MAXN 1000002
#define mod 9987
#define inf 1<<30
using namespace std;
int n,m,zz,head[1002];
struct bian {int frm,to,nx,v;double c;} e[MAXN];
double dis[1002];
int pd[1002],from[1002],q[1002];
void insert(int x,int y,int z)
{
zz++; e[zz].frm=x; e[zz].to=y;
e[zz].v=z; e[zz].c=log(z);
e[zz].nx=head[x]; head[x]=zz;
}
void init()
{
scanf("%d%d",&n,&m);
int i,x,y,z;
for(i=1;i<=m;i++)
{scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
}
}
void spfa()
{
int i,t=0,w=1,x,p;
for(i=1;i<=n;i++) dis[i]=inf;
q[t]=1; dis[1]=0; pd[1]=1;
while(t!=w)
{x=q[t]; t=(t+1)%1000;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(dis[p]>dis[x]+e[i].c)
{dis[p]=dis[x]+e[i].c;
from[p]=i;
if(!pd[p])
{if(dis[p]<=dis[q[t]])
{t=(t+1000-1)%1000; q[t]=p; pd[p]=1;}
else
{q[w]=p; pd[p]=1; w=(w+1)%1000;}
}
}
}
pd[x]=0;
}
i=from[n];
ll ans=1;
while(i!=0)
{ans=(ans*e[i].v)%mod;
i=from[e[i].frm];
}
printf("%lld\n",ans);
}
int main()
{
init(); spfa();
return 0;
}
方案二：spfa+堆，话说只是因为感觉这种算法会快一点点，好像实际上也没有快多少，有些点更慢了。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define MAXN 1000002
#define mod 9987
#define inf 1<<30
using namespace std;
int n,m,zz,head[1002];
struct bian {int frm,to,nx,v;double c;} e[MAXN];
double dis[1002];
int pd[1002],from[1002],q[1002],size;
void insert(int x,int y,int z)
{
zz++; e[zz].frm=x; e[zz].to=y;
e[zz].v=z; e[zz].c=log(z);
e[zz].nx=head[x]; head[x]=zz;
}
void init()
{
scanf("%d%d",&n,&m);
int i,x,y,z;
for(i=1;i<=m;i++)
{scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
}
}
void heapfy(int w)
{
int l=w<<1,r=l+1,minw=w;
if(l<=size&&dis[q[l]]<dis[q[w]]) minw=l;
if(r<=size&&dis[q[r]]<dis[q[minw]]) minw=r;
if(minw!=w)
{swap(q[w],q[minw]); heapfy(minw);}
}
void del()
{
q[1]=q[size]; size--;
if(size) heapfy(1);
}
void weih(int w)
{
while(w>1)
{int i=w>>1;
if(dis[q[w]]<dis[q[i]]) swap(q[w],q[i]);
w=w>>1;
}
}
void spfa()
{
int i,x,p;
for(i=1;i<=n;i++) dis[i]=inf;
q[1]=1; dis[1]=0; pd[1]=1; size=1;
while(size>0)
{x=q[1]; del();
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(dis[p]>dis[x]+e[i].c)
{dis[p]=dis[x]+e[i].c;
from[p]=i;
if(!pd[p])
{q[++size]=p; pd[p]=1; weih(size);}
}
}
pd[x]=0;
}
i=from[n];
ll ans=1;
while(i!=0)
{ans=(ans*e[i].v)%mod;
i=from[e[i].frm];
}
printf("%lld\n",ans);
}
int main()
{
init(); spfa();
return 0;
}
方案三：dijkstra+堆，话说我不会用STL库的东西（太难记了），所以我的代码是手写堆，很长。比以上两种方法快了不少。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define mod 9987
using namespace std;
int n,m,zz,head[1002];
struct bian
{int frm,to,nx,v; double c;} e[1000002];
struct dui{double d;int w;} q[10002];
int pd[1002],size,from[1002];
double dis[1002];
//-----------------------------------------------------------------------------
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-'0'; ch=getchar();}
return x*f;
}
void insert(int x,int y,int z)
{
zz++; e[zz].to=y; e[zz].frm=x;
e[zz].v=z; e[zz].c=log(z);
e[zz].nx=head[x]; head[x]=zz;
}
void init()
{
n=read(); m=read();
int i,x,y,z;
for(i=1;i<=m;i++)
{x=read(); y=read(); z=read();
insert(x,y,z);
}
}
void heapfy(int x)
{
int l=x<<1,r=l+1,minx=x;
if(l<=size&&q[l].d<q[x].d) minx=l;
if(r<=size&&q[r].d<q[minx].d) minx=r;
if(minx!=x)
{swap(q[minx],q[x]); heapfy(minx);}
}
void del()
{
q[1]=q[size]; size--;
if(size) heapfy(1);
}
void weih(int x)
{
if(x<=1) return;
int i=x>>1;
if(q[i].d>q[x].d) swap(q[i],q[x]);
weih(i);
}
void dijkstra()
{
int i,x,p;
for(i=1;i<=n;i++) dis[i]=1e10;
size=1; q[1].d=log(1); q[1].w=1; dis[1]=0;
while(size)
{x=q[1].w; del();
if(pd[x]) continue;
pd[x]=1;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(dis[p]>dis[x]+e[i].c)
{dis[p]=dis[x]+e[i].c;
from[p]=i;
size++; q[size].d=dis[p]; q[size].w=p; weih(size);
}
}
}
ll ans=1;
for(i=from[n];i;i=from[e[i].frm])
ans=(ans*e[i].v)%mod;
printf("%lld\n",ans);
}
int main()
{
init(); dijkstra();
return 0;
}