题目链接：http://icpc.moe/onlinejudge/showProblem.do?problemId=5718
第13届浙江省省赛的题目，题意是给我们一些边的距离与花费，让我们求出所有点到起点(0)的所有最短路距离和，以及达到最短路情况的花费总和，我们采取的思路是先SPFA算出所有点的最短路径，再根据最短路径得出所有可能会建的边，在这些边中找到花费最小的。
注意一点，就是我们的最大值，因为小编的习惯，总是上来就这样定义const int INF = 0x3f3f3f3f，怎么也没想到错就错在这里……题目中的边和是会爆int的TT。我们得把这个最大值再往上调一下。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define LL long long
const int maxn = 100000+5;
const LL INF = 1000000000000005;
struct Edge
{int to,nex;LL dis,cost;
}edge[maxn<<2];
LL dis[maxn],ans1,ans2;
int head[maxn],n,m,cnt;
vector<int> pre[maxn];
queue<int> q;
void addEdge(int u,int v,LL dis,LL cost)
{edge[cnt].to = v;edge[cnt].dis = dis;edge[cnt].cost = cost;edge[cnt].nex = head[u];head[u] = cnt++;
}
void SPFA()
{for(int i=0; i<n; i++){pre[i].clear();dis[i] = INF;}dis[0] = 0;q.push(0);while(!q.empty()){int u = q.front();q.pop();for(int i=head[u]; i!=-1; i=edge[i].nex){int v = edge[i].to;if(dis[v] > dis[u]+edge[i].dis){dis[v] = dis[u]+edge[i].dis;q.push(v);}}}
}
void solve()
{q.push(0);while(!q.empty()){int u = q.front();q.pop();for(int i=head[u]; i!=-1; i=edge[i].nex){int v = edge[i].to;if(dis[v] == dis[u]+edge[i].dis){pre[v].push_back(i);q.push(v);}}}ans1 = ans2 = 0;LL Min;for(int i=0; i<n; i++){ans1 += dis[i];Min = INF;for(int j=0; j<pre[i].size(); j++)Min = min(Min, edge[pre[i][j]].cost);if(Min == INF) continue;ans2 += Min;}printf("%lld %lld\n",ans1,ans2);
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);cnt = 0;memset(head,-1,sizeof(head));int a,b;LL cost,dis;for(int i=0; i<m; i++){scanf("%d%d%lld%lld",&a,&b,&dis,&cost);addEdge(a,b,dis,cost);addEdge(b,a,dis,cost);}SPFA();solve();}return 0;
}