【洛谷 2384】最短路

向右看齐 2021-10-24 04:56 251阅读 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

题解：简单的dijkstra对就这样，加法改成乘法。

（看错题目，有向图以为无向，哎找了好久）

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    typedef long long ll;
    using namespace std;
    const int oo=2147483647;
    const int mod=9987;
    int n,m,dis[5005],vis[5005],a[5005][5005];
    int main(){
        freopen("2384.in","r",stdin);
        freopen("2384.out","w",stdout);
        scanf("%d %d",&n,&m);
        int x,y,z;
        //memset(a,100000,sizeof(a));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=100000;
        for(int i=1;i<=m;i++){
            cin>>x>>y>>z;
            a[x][y]=z;
            //a[y][x]=z;
        }
        for(int i=1;i<=n;i++)
            dis[i]=a[1][i];
        dis[1]=0;
        vis[1]=1;
        for(int i=1;i<=n;i++){
            int now=oo,ii;
            for(int j=1;j<=n;j++)
                if(vis[j]==0 && dis[j]<now){
                    ii=j; now=dis[j];
                }
            vis[ii]=1;
            for(int j=1;j<=n;j++)
                if(dis[ii]*a[ii][j]<dis[j])
                   dis[j]=dis[ii]*a[ii][j];
        }
        cout<<dis[n]%mod<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11141326.html