撰写时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 11 测试通过 : 0
比赛描述
oo和他的同学有了一个越狱计划，只要逃跑成功则可以通过火车脱离险境，然而敌人会对这条逃跑路线有了防范，派人埋伏在这些道路上。被埋伏的道路则无法通过。oo决定趁信息差先让他的同学逃跑，他再逃跑。oo会和同学一起，坐上火车，踏上自由之路。为了尽快逃脱，他们需要寻找一个最快的逃跑方案。 如果他们跑不了，输出you can not
输入
第一行一个整数T表示case个数(1<=T<=10)，每个case一个整数n (2 ≤ n ≤ 100)表示路口的数量，第二行一个m表示道路的数量，接下来m行，每行3个整数，表示道路两头的两个路口和这条道路所要花费的时间，这个时间不会大于1000。他们所在的路口是1，火车站的路口是n。
输出
如果可以逃脱，输出一个整数表示最快的方案所需要的时间。如果不能，输出you can not
样例输入
2
2
1
1 2 999
3
3
1 3 10
2 1 20
3 2 50
样例输出
you can not
80
/*
ID: oodt
PROG:
LANG:C++
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<cassert>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int maxx=10005;
int n,m,k;
int a[maxx];
int ans = 0,cnt = 0,pos = 0;
int l = 0,r = 0;
const int MAXN = 100005;
const int MAXM = 1000005;
const int INF = 0x3f3f3f3f;
struct Edge{
int to,next,cap,flow,cost;
}edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;
void init(int n){
N = n;
tol = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost){
edge[tol].to = v;edge[tol].cap = cap;edge[tol].flow = 0;edge[tol].cost = cost;
edge[tol].next = head[u];head[u] = tol++;
edge[tol].to = u;edge[tol].cap = 0;edge[tol].flow = 0;edge[tol].cost = -cost;
edge[tol].next = head[v];head[v] = tol++;
}
bool spfa(int s,int t){
queue<int> q;
rep(i,0,N){
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost){
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -1) return false;
else return true;
}
int mincostmaxflow(int s,int t,int &cost){
int flow = 0;
cost = 0;
while(spfa(s,t)){
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]){
if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow;
}
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]){
edge[i].flow += Min;
edge[i^1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
int main()
{
#ifdef LOCAL
freopen("/Users/ecooodt/Desktop/c++ and acm/_闆嗚2/talk_3/a/1.in","r",stdin);
freopen("/Users/ecooodt/Desktop/c++ and acm/_闆嗚2/talk_3/a/1.out","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
init(n+1);
scanf("%d",&m);
rep(i,0,m){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
addedge(u,v,1,c);
addedge(v,u,1,c);
}
addedge(0,1,2,0);
ans = 0;
int t = mincostmaxflow(0,n,ans);
if(t >= 2) printf("%d\n",ans);
else printf("you can not\n");
}
return 0;
}