我TM建个前向星的双向边MAXN只开100005？？？还一直不报WA，一直以为我是哪里没考虑到。。。。
一定要注意数组大小了。思路很简单，从0到其他点的最短路距离是一定的，那要求最小花费，那就边跑最短路边更新最小花费呗。
#include<cstdio> #include<cstdlib> #include<iostream> #include<string> #include<set> #include<algorithm> #include<vector> #include<queue> #include<list> #include<cmath> #include<cstring> #include<map> #include<stack> using namespace std; #define INF 0x3f3f3f3f #define maxn 200005 #define ull unsigned long long #define ll long long #define hashmod 99999839 #define mod 7 #define repe(x,y,i) for(i=x;i<=y;++i) #define repne(x,y,i) for(i=x;i<y;++i) #define MAX(x,y) (x) < (y) ? (y) : (x); #define MIN(x,y) (x) < (y) ? (x) : (y); int n,m,x,y,d,c; struct edge{ int to,d,c,next; }G[maxn]; int head[maxn],len; ll dis[maxn],micost[maxn]; bool vis[maxn]; void addedge(){ G[len].to = y,G[len].d = d,G[len].c = c,G[len].next = head[x]; head[x] = len; len++; G[len].to = x,G[len].d = d,G[len].c = c,G[len].next = head[y]; head[y] = len; len++; } void SPFA(){ queue<int> q; memset(dis,0x3f,sizeof(dis)); memset(micost,0x3f,sizeof(micost)); memset(vis,false,sizeof(vis)); q.push(0); dis[0] = micost[0] = 0; vis[0] = true; while(!q.empty()){ int v = q.front(); q.pop(); vis[v] = false; for(int i = head[v];i != -1;i = G[i].next){ edge& t = G[i]; if(dis[t.to] > dis[v] + t.d){ dis[t.to] = dis[v] + t.d; micost[t.to] = t.c; if(!vis[t.to]) q.push(t.to); } else if(dis[t.to] == dis[v] + t.d && micost[t.to] > t.c) micost[t.to] = t.c; } } } int main(){ // freopen("a.in","r",stdin); // freopen("b.out","w",stdout); int T; register int i,j; cin >> T; while(T--){ scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); len = 0; repe(1,m,i){ scanf("%d%d%d%d",&x,&y,&d,&c); addedge(); } SPFA(); ll sc,st; sc = st = 0; repne(0,n,i) st += dis[i],sc += micost[i]; printf("%lld %lld ",st,sc); } return 0; }