首先看题看的很懵..

然后这题直接没想用Djstra做 TLE了。看discuss，Dijstra要用堆优化，也可以用SPFA做。

这里在网上找了这两种做法的区别，点多稠密图用Dij，以为它是操作点的，反之则用SPFA。

好久没做题了，前一段时间尽做水题去了。

还有这一道题的数据巨大，各种WA。要用__int64，同时SPFA中要注意环的问题。dis的初始化也要注意全部初始为无穷大。

先给出SPFA的AC代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAXN 50010#define MAXM 200010#define inf 20000000000struct Node{    int v,next;    __int64 c;}edge[MAXM];bool flag;int que[MAXM];int head[MAXN];int tail[MAXN];__int64 dis[MAXN];bool vis[MAXN];int a[MAXN];int fa[MAXN];int n,m,e;void addEdge(int u,int v,int c){    edge[e].v=v;    edge[e].c=c;    edge[e].next=head[u];    head[u]=e;    e++;    edge[e].v=u;    edge[e].c=c;    edge[e].next=head[v];    head[v]=e;    e++;}void spfa(int s){    memset(vis,false,sizeof(vis));    memset(fa,0,sizeof(fa));    for(int i=0;i
         
          dis[pre]+edge[j].c) { dis[v]=dis[pre]+edge[j].c; if(!vis[v]) { vis[v]=true; que[rear++]=v; } } } vis[pre]=false; }}int main(){ int T; scanf("%d",&T); while(T--) { e=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=0;i