题意:给定m<=50000的1-n有联通的图,求最多可以使K<=20条边变为0的情况下的最短路是多少。。

思路:简单的分层图最短路,对于每个点拆成K个点。。

然后求一边最短路。。

code:

/* * Author: Yzcstc * Created Time: 2014/11/5 19:25:47* File Name: revamp.cpp */#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<string>#include<map>#include<set>#include<vector>#include<queue>#include<stack>#include<ctime>#define M0(x) memset(x,0,sizeof(int)*(n+10))#define MP make_pair#define x first#define y secondusingnamespace std;typedeflonglong ll;typedef pair<ll,int> pii;constint maxn =;struct edge{int v, w,next;} e[maxn *];intlast[maxn], tot;int n, k, m;void add(constint&u,constint&v,constint& w){ e[tot]=(edge){v, w,last[u]};last[u]= tot++;}void init(){int u, v, w; memset(last,-,sizeof(int)*(n * k +)); tot =;for(int i =; i < m;++i){ scanf(“%d%d%d”,&u,&v,&w); add(u, v, w); add(v, u, w);for(int i =; i <= k;++i){ add(u + i * n, v + i * n, w); add(v + i * n, u + i * n, w); add(u +(i-)* n, v + i * n,); add(v +(i-)* n, u + i * n,);}}} ll dis[maxn];int vis[maxn];void dij(){ priority_queue<pii, vector<pii>, greater<pii>> q;int nt = n * k + n; memset(vis,,sizeof(vis));for(int i =; i <= nt;++i)dis[i]=(1LL<<); pii tmp(,); dis[]=; q.push(tmp);int u, v;while(!q.empty()){ u = q.top().y; q.pop();if(vis[u])continue; vis[u]=;for(int p =last[u];~p; p = e[p].next){ v = e[p].v;if(dis[u]+ e[p].w < dis[v]){ dis[v]= dis[u]+ e[p].w; tmp.x = dis[v], tmp.y = v; q.push(tmp);}}}}void solve(){ dij(); ll ans =1LL<<;for(int i =; i <= k;++i) ans = min(ans, dis[n+i*n]); cout << ans << endl;}int main(){ freopen(“a.in”,“r”, stdin); freopen(“a.out”,“w”, stdout);clock_t start, finish; start = clock();while(scanf(“%d%d%d”,&n,&m,&k)!= EOF){ init(); solve();} finish = clock();double t =(double)(finish start)/ CLOCKS_PER_SEC;// printf(“time = %.6f\n”, t);return;}

发表回复

您的电子邮箱地址不会被公开。