「codecomb2090」最小乘积路

给定n个点的带权有向图，求从1到n的路径中边权之积最小的简单路径。

输入格式

第一行读入两个整数n，m，表示共n个点m条边。

接下来m行，每行三个正整数x，y，z，表示点x到点y有一条边权为z的边。

输出格式

输出仅包括一行，记为所求路径的边权之积，由于答案可能很大，因此输出它模9987的余数即可。

样例数据 1

输入

3 3
1 2 3
2 3 3
1 3 10

输出

9

备注

对于20%的数据，n<=10。

对于100%的数据，n<=1000，m<=1000000。边权不超过10000。

题解

边权相乘会爆，所以取对数变成相加

找到最短路后暴力算答案

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#define inf 1000000000
#define mod 9987
#define ll unsigned long long
#define pa pair<long double,int>
using namespace std;
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;
}
int n,m,cnt;
int last[1005],from[1005];
long double dis[1005];
bool vis[1005];
struct data{int to,next,from,t;long double v;}e[1000005];
void insert(int u,int v,long double w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
	e[cnt].from=u;e[cnt].t=w;e[cnt].v=log(w);
}
void dijkstra()
{
	priority_queue<pa,vector<pa>,greater<pa> > q;
	for(int i=1;i<=n;i++)dis[i]=1e60;
	dis[1]=log(1.0);q.push(make_pair(log(1.0),1));
	while(!q.empty())
	{
		int now=q.top().second;q.pop();
		if(vis[now])continue;vis[now]=1;
		for(int i=last[now];i;i=e[i].next)
		{
			if(dis[e[i].to]>dis[now]+e[i].v)
			{
				from[e[i].to]=i;
				dis[e[i].to]=dis[now]+e[i].v;
				q.push(make_pair(dis[e[i].to],e[i].to));
			}
		}
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		u=read();v=read();w=read();
		insert(u,v,w);
	}
	dijkstra();
	int ans=1;
	for(int i=from[n];i;i=from[e[i].from])
		ans=(ans*e[i].t%mod);
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#define inf 1000000000

#define mod 9987

#define ll unsigned long long

#define pa pair<long double,int>

using namespace std;

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;

}

int n,m,cnt;

int last[1005],from[1005];

long double dis[1005];

bool vis[1005];

struct data{int to,next,from,t;long double v;}e[1000005];

void insert(int u,int v,long double w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

e[cnt].from=u;e[cnt].t=w;e[cnt].v=log(w);

}

void dijkstra()

{

priority_queue<pa,vector<pa>,greater<pa> > q;

for(int i=1;i<=n;i++)dis[i]=1e60;

dis[1]=log(1.0);q.push(make_pair(log(1.0),1));

while(!q.empty())

{

int now=q.top().second;q.pop();

if(vis[now])continue;vis[now]=1;

for(int i=last[now];i;i=e[i].next)

{

if(dis[e[i].to]>dis[now]+e[i].v)

{

from[e[i].to]=i;

dis[e[i].to]=dis[now]+e[i].v;

q.push(make_pair(dis[e[i].to],e[i].to));

}

int main()

{

n=read();m=read();

for(int i=1;i<=m;i++)

{

int u,v,w;

u=read();v=read();w=read();

insert(u,v,w);

}

dijkstra();

int ans=1;

for(int i=from[n];i;i=from[e[i].from])

ans=(ans*e[i].t%mod);

printf("%d",ans);

return 0;

}

hzwer.com _ Home | http://hzwer.com

题目描述

输入格式

输出格式

样例数据 1

备注

分类目录

热门文章

Myfriends

近期评论