最短路问题,牛客比赛

问题遇到的现象和发生背景

img


img

题目链接:https://ac.nowcoder.com/acm/contest/39100/F

问题相关代码,请勿粘贴截图
#include
#include
#include
#include
#include
#include
#include
#define int long long

using namespace std;
const int N=200010,mod=998244353;

int e[N],w[N],ne[N],h[N],idx,shu[N],d[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void doo()
{
    memset(d,0x3f,sizeof d);
    priority_queueint,int>,vectorint,int>>,greaterint,int>> >q;
    d[1]=0;
    q.push({0,1});
    while(q.size())
    {
        int t=q.top().second;
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]>d[t]+w[i])
            {
                d[j]=d[t]+w[i];
                q.push({d[j],j});
            }
        }
    }
}

signed main()
{
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    int x,y,z;
    cin>>x>>y>>z;
    for(int i=1;i<=n;i++)cin>>shu[i];
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        if(shu[u]==shu[v])add(u,v,min(x,y+z)),add(v,u,min(x,y+z));
        else add(u,v,min(y,x+z)),add(v,u,min(y,x+z));
    }
    doo();
    cout<
运行结果及报错内容

不明白自己的代码为啥错误,请帮忙看一看

目前看代码明面上的错误有:

  1. N定义小了,是双向路,应该再乘以2.
  2. 最短路里面没有标记访问的点,应该再开一个vis数组记录
  3. 数据量达到了2e5级别了,用scanf会明显快很多
  4. dis数组类型应该是long long,初始化用0x7f比较好

其余的需要运行一下了