最短路问题，牛客比赛

Question

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

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

问题相关代码，请勿粘贴截图

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#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_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,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<<d[n]<<endl;
}

运行结果及报错内容

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

Answer 1

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

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

其余的需要运行一下了