题意:一群学生去城市的各个车站发邀请函,每个车站恰有一个学生。任意两个车站之间都可达,并且有一个特定的车费。假如学生们早上都从车站1出发,晚上从各个车站回到车站1,求总的最小花费。
题解:人生第一道Spfa。题意很明确,求带权最短路径。回来的时候反向建图即可。
#include <queue> #include <iostream> using namespace std; #define N 1000001 #define INF 1999999999 struct Edge { int v, w, next; } edgeGo[N], edgeBack[N]; int P, Q; int dis[N]; int headGo[N], headBack[N]; bool mark[N]; queue<int>que; void spfa ( Edge edge[], int head[] ) { memset(mark,0,sizeof(mark)); while ( ! que.empty() ) que.pop(); int i, u, v; for ( i = 1; i <= P; i++ ) dis[i] = INF; dis[1] = 0; mark[1] = 1; que.push(1); while ( !que.empty () ) { u = que.front(); que.pop(); mark[u] = 0; for ( i = head[u]; i != 0; i = edge[i].next ) { v = edge[i].v; if ( dis[v] > dis[u] + edge[i].w ) { dis[v] = dis[u] + edge[i].w; if ( ! mark[v] ) { que.push ( v ); mark[v] = 1; } } } } } int main() { int t, k, u, v, w; scanf("%d",&t); while ( t-- ) { k = 0; memset(headGo,0,sizeof(headGo)); memset(headBack,0,sizeof(headBack)); scanf("%d%d",&P,&Q); while ( Q-- ) { scanf("%d%d%d",&u,&v,&w); k++; edgeGo[k].v = v; edgeGo[k].w = w; edgeGo[k].next = headGo[u]; headGo[u] = k; edgeBack[k].v = u; edgeBack[k].w = w; edgeBack[k].next = headBack[v]; headBack[v] = k; } int i; __int64 ans = 0; spfa ( edgeGo, headGo ); for ( i = 1; i <= P; i++ ) ans += dis[i]; spfa ( edgeBack, headBack ); for ( i = 1; i <= P; i++ ) ans += dis[i]; printf("%I64d\n",ans); } return 0; }