总体思路：用dis[u]+w<dis[v]的思路优化一些本来的广搜即可

题目链接

#include<bits/stdc++.h>
using namespace std;
long long mod;
long long s,t;
long long a,b,c;
long long w[3000004];
long long vis[3000005];
int main(){
    memset(vis,0x3f,sizeof vis);
    cin>>mod>>s>>t>>a>>b>>c;
    cin>>w[1]>>w[2]>>w[3];
    queue<long long>q;
    q.push(s);
    vis[s]=0;
    while(q.size()){
        long long now=q.front();
        q.pop();
        long long x=(now+a)%mod;
        if(vis[now]+w[1]<vis[x]){
            q.push(x);
            vis[x]=vis[now]+w[1];
        }
        x=(now-b+mod)%mod;
        if(vis[now]+w[2]<vis[x]){
            q.push(x);
            vis[x]=vis[now]+w[2];
        }
        x=now*c%mod;
        if(vis[now]+w[3]<vis[x]){
            q.push(x);
            vis[x]=vis[now]+w[3];
        }
    }
    if(vis[t]<1e15){
        cout<<vis[t];
    }else{
        cout<<-1;
    }
    return 0;
}