25 分（RE #1,2,3）求助

用的是堆优化 Dijkstra。不知道为啥 RE 了 3 个点。

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxN=1000005,maxM=maxN,INF=0x3f3f3f3f;
struct Edge {int to,val,nxt;}edge[maxM][2];
struct Node {
    int to,dis;
    friend bool operator < (Node a,Node b) {
        return a.dis>b.dis;
    }
};
priority_queue<Node> q[2];
int n,m,tot,hd[maxN][2],vis[maxN];
ll dis[maxN];
void rd(int&),addedge(int,int,int,int),dij(int);
int main() {
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    rd(n);rd(m);
    for (;m;m--) {
        int u,v,w;rd(u);rd(v);rd(w);
        addedge(0,u,v,w);
        addedge(1,v,u,w);
    }
    ll ans=0; 
    dij(0);for (int i=2;i<=n;i++) ans+=dis[i];
    memset(vis,false,sizeof vis);
    dij(1);for (int i=2;i<=n;i++) ans+=dis[i];
    printf("%lld\n",ans);
    return 0;
}
void rd(int& x) {
    x=0;char ch=getchar();
    while (ch<48||ch>57) ch=getchar();
    while (ch>47&&ch<58) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}
void addedge(int k,int x,int y,int v) {
    edge[++tot][k].to=y;
    edge[tot][k].val=v;
    edge[tot][k].nxt=hd[x][k];
    hd[x][k]=tot;
}
void dij(int k) {
    memset(dis,INF,sizeof dis);
    dis[1]=0ll;
    while (!q[k].empty()) q[k].pop();
    Node S;
    S.to=1;S.dis=0;
    q[k].push(S);
    while (!q[k].empty()) {
        Node T=q[k].top();
        q[k].pop();
        int u=T.to,d=T.dis;
        if (vis[u]) continue;
        vis[u]=1;
        for (int i=hd[u][k];i;i=edge[i][k].nxt) {
            int o=edge[i][k].to;
            if (dis[o]>dis[u]+edge[i][k].val) {
                dis[o]=dis[u]+edge[i][k].val;
                Node nxt;
                nxt.to=o;nxt.dis=dis[o];
                q[k].push(nxt);
            }
        }
    }
}