Problem Description
The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as N towns and M roads, and each road has the same length and connects two towns. The town numbered 1 is where general’s castle is located, and the town numbered N is where the enemies are staying. The general supposes that the enemies would choose a shortest path. He knows his army is not ready to fight and he needs more time. Consequently he decides to put some barricades on some roads to slow down his enemies. Now, he asks you to find a way to set these barricades to make sure the enemies would meet at least one of them. Moreover, the barricade on the i-th road requires wi units of wood. Because of lacking resources, you need to use as less wood as possible.

Input
The first line of input contains an integer t, then t test cases follow.
For each test case, in the first line there are two integers N(N≤1000) and M(M≤10000).
The i-the line of the next M lines describes the i-th edge with three integers u,v and w where 0≤w≤1000 denoting an edge between u and v of barricade cost w.

Output
For each test cases, output the minimum wood cost.

Sample Input
1
4 4
1 2 1
2 4 2
3 1 3
4 3 4

Sample Output
4

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <list>
using namespace std;
#define LL long long
#define MAXN 1005
struct node
{
int v,len,w; //终点、长度
node(int a,int b,int c){
v = a,len = b,w = c;
}
};
struct edge
{
int to,cap,rev;
edge(int a,int b,int c){
to = a,cap = b,rev = c;
}
};
int n;
vector <node> g[MAXN];
vector <edge> G[MAXN];
int d[MAXN];
bool used[MAXN];//DFS中用到的访问标记
{
G[u].push_back(edge(v,cap,G[v].size()));
G[v].push_back(edge(u,0,G[u].size()-1));
}
//通过DFS寻到增广路
int dfs(int v,int t,int f){
if(v == t)
return f;
used[v] = true;
for(int i = 0; i < G[v].size(); i++){
edge &e = G[v][i];
if(!used[e.to] && e.cap > 0){
int d = dfs(e.to,t,min(f,e.cap));
if(d > 0){
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

//求解从s到t的最大流
int max_flow(int s,int t){
int flow = 0;
while(1){
memset(used,false,sizeof(used));
int f = dfs(s,t,99999999);
if(f == 0)
return flow;
flow += f;
}
}

void solve()
{
for (int i = 1; i <= n; i++)
{
int len = g[i].size();
for (int j = 0; j < len; j++)
{
int v = g[i][j].v;
int l = g[i][j].len;
int w = g[i][j].w;
if (d[v] - d[i] == l) //判断是不是为最短路
{
}
}
}
}

void SPFA(int x) //x为出发点
{
int v[MAXN];
memset(v,0,sizeof(v));
queue<int>q;
q.push(x);
v[x] = 1;d[x] = 0;
while(!q.empty())
{
int nod = q.front();
q.pop();
v[nod] = 0;
for(int i = 0;i < g[nod].size();i++)
{
int nxtnod = g[nod][i].v;
if(d[nxtnod] > d[nod] + g[nod][i].len)
{
d[nxtnod] = d[nod] + g[nod][i].len;
if(!v[nxtnod])
{
v[nxtnod] = 1;
q.push(nxtnod);
}
}
}
}
}
void init()
{
memset(d,1,sizeof(d));
for (int i = 0; i < MAXN-1; i++)
{
g[i].clear();
G[i].clear();
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
int m;
cin >> n >> m;
init();

for (int i = 0; i < m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(node(v,1,w));
g[v].push_back(node(u,1,w));
}
SPFA(1);
solve();
long long ans = max_flow(1,n);
printf("%lld\n",ans);
}
return 0;
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！