AC日记——最短路洛谷 P2384

我不是女神ヾ 2021-12-18 06:01 283阅读 0赞

## 题目背景 ##

狗哥做烂了最短路，突然机智的考了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：

## 说明 ##

好好看一看再写哟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<<1];
    
    int if_z,head[maxn],n,m,cnt;
    int dis[maxn],que[maxm<<2];
    
    bool if_[maxn];
    
    char Cget;
    
    inline void in(int &now)
    {
        now=0,if_z=1,Cget=getchar();
        while(Cget>'9'||Cget<'0')
        {
            if(Cget=='-') if_z=-1;
            Cget=getchar();
        }
        while(Cget>='0'&&Cget<='9')
        {
            now=now*10+Cget-'0';
            Cget=getchar();
        }
        now*=if_z;
    }
    
    int main()
    {
        in(n),in(m);int u,v,w;
        for(int i=1;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=0,tail=0;
        for(int i=1;i<=n;i++) dis[i]=0x7fffffff;
        que[tail++]=1,if_[1]=true,dis[1]=1;
        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]%9987;
        return 0;
    }

转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6504421.html