C++(g++ 7.5.0) 解法, 执行用时: 887ms, 内存消耗: 8204K, 提交时间: 2023-03-05 17:20:22

#include <iostream>
#define inf 0x3f3f3f
long long a[1010][1010];
int main()
{
    long long k,i,j,n,m;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j)a[i][j]=0;
            else a[i][j]=inf;
    long long fr,ed,l;
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&fr,&ed,&l);
        a[fr][ed]=l;
    }
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(a[i][j]>a[i][k]*a[k][j]&&a[i][k]*a[k][j]!=0)
                    a[i][j]=(a[i][k]*a[k][j])%9987;
    printf("%lld",a[1][n]);
    return 0;
}

C++ 解法, 执行用时: 20ms, 内存消耗: 732K, 提交时间: 2021-11-25 17:13:19

#include<bits/stdc++.h>
using namespace std;
const int N = 1010,mod=9987;
typedef pair<int,int> pll;
vector<pll> a[N];
int n,m;
int maxn=1e9;
void dfs(int x,int y)
{
    if(x==n)
    {
        maxn=min(maxn,y);
    }
    for(auto k:a[x])
    {
        y=k.second*y;
        dfs(k.first,y);
    }
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int q,w,e;
        cin>>q>>w>>e;
        a[q].push_back(make_pair(w,e));
        
    }dfs(1,1);
        cout<<maxn%mod;
        return 0;
}