突然意识到以前写的都是假的dij，感谢GhostCai神犇。

#include
      
       #include
       
        #include
        
         #include
         
          #define int long longusing namespace std;const int MAXN = 10005;const int MAXM = 500005;const int inf = 2147483647;inline int rd(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return f?x:-x;}int n,m,S,dis[MAXN],head[MAXN],cnt;int to[MAXM],nxt[MAXM],val[MAXM];bool vis[MAXN];struct Node{    int id,w;    friend bool operator<(const Node A,const Node B){        return A.w>B.w;    }};inline void add(int bg,int ed,int w){    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt,val[cnt]=w;}priority_queue
          
            Q;void dijkstra(){    for(int i=1;i<=n;i++) dis[i]=inf;    Node now;now.id=S;now.w=0;dis[S]=0;    int p,ww;Q.push(now);    while(!Q.empty()){        Node x=Q.top();Q.pop();p=x.id;ww=x.w;        if(vis[p] || dis[p]!=ww) continue;        vis[p]=1;int u;        for(register int i=head[p];i;i=nxt[i]){            u=to[i];            if(dis[p]+val[i]