Path HDU - 6582 2019 Multi-University Training Contest 1

Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.

After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.

Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl’s home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.

Note, if Jerry can’t reach his girl’s house in the very beginning, the answer is obviously zero. And you don’t need to guarantee that there still exists a way from Jerry’s house to his girl’s after blocking some edges.

input

The input begins with a line containing one integer T(1≤T≤10), the number of test cases.

Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.

m lines follow, each of which consists of three integers x,y,c(1≤x,y≤n,1≤c≤10^9), denoting that there exists a one-way road from the house indexed x to y of length c.

output

Print T lines, each line containing a integer, the answer.

sample input

1

3 4

1 2 1

2 3 1

1 3 2

1 3 3

sample output

3

題目大意：T組資料，n個城市，m條路，并且是單向邊，每條邊都有一個權值花費，題目是這樣說的Jerry想去找他的女票，但是Jerry的小夥伴Tom想阻撓Jerry去找女票，Tom阻斷最短路徑上的路，讓Jerry走的更遠，阻斷路徑肯定是需要花費的問，問讓Jerry走的更遠的前提下，最小的花費是多少。

分析：

其實這題是一個闆子題—網絡流值最小割問題，知道網絡流最大的流等于最小割的話，這題剩下的就是建圖了，怎麼建圖模組化是網絡流的關鍵；

這樣來分析，Tom不是想讓Jerry走更遠的路嗎，就是不想讓Jerry走最短路呗，那麼就看一下，有哪些邊是構成最短路徑上的路徑不就好了（注意哦，最短路的長度雖然一樣，但是走的路徑不一定一樣，就像本題中所給的樣例一樣，最短路可以是1–2--3 或者1–3），這樣的話我們獲得的這些路徑就可以建成一個新的圖，就可以用這個圖跑一個網絡流求最小割的闆子了（最小割就是求最小需要付出的代價是多少才能使源點不能到彙點）

其中需要特判的是如果本事就不存在最短路，那麼就輸出0

還有要注意用long long

參考代碼：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstring>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define rep(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
using namespace std;
int n,m;
int s,t;
const int N=1e4+100;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct node{
    int to;ll val;
};
ll dis1[N],dis2[N];
bool inq[N];
vector<node>ve[N],ve2[N];

void SPFA1(){//正向跑一遍最短路
    memset(inq,0,sizeof inq);
    rep(i,1,n) dis1[i]=INF;
    queue<int>q;
    dis1[s]=0;
    inq[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<ve[u].size();i++){
            int to=ve[u][i].to;
            ll val=ve[u][i].val;
            if(dis1[to]>dis1[u]+val){
                dis1[to]=dis1[u]+val;
                if(!inq[to]){
                    q.push(to);
                    inq[to]=1;
                }
            }
        }
        inq[u]=0;
    }
}

void SPFA2(){//反向跑一遍最短路
    memset(inq,0,sizeof inq);
    rep(i,1,n) dis2[i]=INF;
    queue<int>q;
    dis2[n]=0;
    inq[n]=1;
    q.push(t);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<ve2[u].size();i++){
            int to=ve2[u][i].to;
            ll val=ve2[u][i].val;
            if(dis2[to]>dis2[u]+val){
                dis2[to]=dis2[u]+val;
                if(!inq[to]){
                    q.push(to);
                    inq[to]=1;
                }
            }
        }
        inq[u]=0;
    }
}
struct Edge{
    ll from,to,cap,flow;
};
vector<int>G[N];
vector<Edge>edge;
bool vis[N];
ll d[N];
int cur[N];
void add(int u,int v,ll val){
    edge.push_back((Edge){u,v,val,0});
    edge.push_back((Edge){v,u,0,0});
    int cnt=edge.size();
    G[u].push_back(cnt-2);
    G[v].push_back(cnt-1);
}
bool bfs(){
       
    memset (vis,0,sizeof vis) ;
    queue<int> Q;
    Q.push(1);
    d[1]=0;
    vis[1]=1;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=0;i<G[x].size();i++){
            Edge & e=edge[G[x][i]];
            if(!vis[e.to] && e.cap>e.flow){
                vis[e.to]=1;
                d[e.to]=d[x]+1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}

ll dfs(int x, ll a){
    if(x==t|| a==0) return a;
    ll flow=0,f;
    for(int & i=cur[x];i<G[x].size();i++){
        Edge & e=edge[G[x][i]];
        if(d[x]+1 == d[e.to] && (f= dfs(e.to,min(a, e.cap-e.flow)))>0){
            e.flow+=f;
            edge[G[x][i]^1].flow-=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}
ll dinic(){
  ll ans=0;
 memset(d,0,sizeof d);
    while(bfs()){
        memset(cur ,0 ,sizeof cur);
        ans+= dfs(s,INF);
    }
    return ans;
}
void init(){
    s=1;t=n;
    for(int i=0;i<=10000;i++) ve[i].clear();
    for(int i=0;i<=10000;i++) ve2[i].clear();
    for(int i=0;i<=10000;i++) G[i].clear();
    edge.clear();
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);

        init();

        for(int i=1;i<=m;i++){int u,v;ll w;
            scanf("%d%d%lld",&u,&v,&w);
            if(u==v) continue;
            ve[u].push_back((node){v,w});
            ve2[v].push_back((node){u,w});
        }

        SPFA1();
        if(dis1[n]==INF){
            printf("0\n");
            continue;
        }

        SPFA2();

        for(int i=1;i<=n;i++){
            for(int j=0;j<ve[i].size();j++){
                int to=ve[i][j].to;
                ll val=ve[i][j].val;
                if(dis1[i]+dis2[to]+val==dis1[n]){
                    add(i,to,val);//網絡流建圖
                }
            }
        }
        printf("%lld\n",dinic());
    }
//    cout<<INF<<endl;
    return 0;
}