16年zj省赛的一道题目……当时没做出来，因为没有理解SPFA的真正本质……
题意是给你一个无向图，每条边有两个权值（时间、费用），要求在从0到任意点时间最短的情况下使用尽可能少的费用。。
首先需要知道的是做完最短路后每个点的前驱只可能有一个。
裸的SPFA，在edge上再增加一个值，每次先判断能不能使得d[u]更小，如果能，就更新，同时用数组sv来记录每个点的前驱边的花费是多少，如果相等，就把sv取尽可能小。
这样做完之后每个点的sv值之和就是所有选取的边的费用总合，d值之和就是花费时间总合……真的好傻逼……我竟然没有做出来……心痛啊！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
#define UB upper_bound
#define LB lower_bound
#define MP make_pair
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<vi>
#define mst(x,y) memset(x,y,sizeof(x))
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define sp system("pause")
#define iin(x) scanf("%d",&x)
#define INF 1e18
#define MAXN 100005
#define hash hhash
#define PI acos(-1.0)
#define eps 1e-4
const int mod = 1e9+7;
#define SIZE 200005
struct node
{
int v;
ll tim,cost;
node(int vv,ll timee,ll costt)
{
v = vv,tim = timee,cost = costt;
}
};
vector<node>g[SIZE];
int n,m;
ll sv[SIZE],sum2;
ll tim[SIZE],vis[SIZE],d[SIZE];
void SPFA()
{
queue<int>q;
mst(vis,0);mst(sv,0);
for(int i = 0;i < SIZE;i++) d[i] = INF,tim[i] = INF;
d[0] = 0,vis[0] = 1,q.push(0),tim[0] = 0;
while(!q.empty())
{
int u = q.front();
vis[u] = 0;
q.pop();
for(int i = 0;i < g[u].size();i++)
{
int te = g[u][i].v;
ll tm = g[u][i].tim;
ll co = g[u][i].cost;
if(d[te] > co + d[u])
{
d[te] = co + d[u];
sv[te] = tm;
if(!vis[te])
vis[te] = 1,q.push(te);
}
else if(d[te] == co + d[u])
{
sv[te] = min(sv[te],tm);
//tim[te] = tim[u] + tm;
if(!vis[te])
vis[te] = 1,q.push(te);
}
}
}
for(int i = 0;i < n;i++)
sum2 += d[i];
}
int main()
{
int t;
cin >> t;
while(t--)
{
sum2 = 0;
cin >> n >> m;
for(int i = 0;i < n;i++)
g[i].clear();
for(int i = 0;i < m;i++)
{
int a,b;
ll c,d;
scanf("%d %d %lld %lld",&a,&b,&d,&c);
g[a].PB(node(b,c,d));
g[b].PB(node(a,c,d));
}
SPFA();
ll sum1 = 0;
for(int i = 0;i < n;i++)
sum1 += sv[i];
cout << sum2 << " " << sum1 << endl;
}
return 0;
}