1579: [Usaco2009 Feb]Revamping Trails 道路升级
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 2206 Solved: 622
[Submit][Status][Discuss]
Description
每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i 走到P１_i 他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <= K <= 20)条路经，将它们所须时间减为０．帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.
Input
* 第一行: 三个空格分开的数: N, M, 和 K * 第2..M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i
Output
* 第一行: 更新最多Ｋ条路经后的最短路经长度．
Sample Input
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
1 2 10
2 4 10
1 3 1
3 4 100
Sample Output
1
HINT
K是1; 更新道路3->4使得从３到４的时间由１００减少到０. 最新最短路经是1->3->4,总用时为１单位. N<=10000
题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=1579
Solution
f [ i ] [ j ] 表示修改了 i 次，从 1 到 i 的最短路。。。
然后做法就很显然了。。。每次先枚举修改哪条边，然后跑一遍最短路。。。
之前写spfa莫名爆炸。。最后只好用dijkstra水过。。。。。。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define N 2000050
#define LL long long
using namespace std;
int n,m,k,cnt=0;
struct edge{
int r,nxt,v;
}e[200000];
bool vis[N];
int f[N],d[N];
int hed[N];
void insert(int u,int v,int w){
e[++cnt].r=v;e[cnt].v=w;e[cnt].nxt=hed[u];hed[u]=cnt;
e[++cnt].r=u;e[cnt].v=w;e[cnt].nxt=hed[v];hed[v]=cnt;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
void spfa(){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
if(f[i]==-1)continue;
Q.push(make_pair(f[i],i) );
}
int now;
LL G;
while( !Q.empty() ){
now=Q.top().second;
G=Q.top().first;
Q.pop();
if(vis[now])continue;
vis[now]=1;
for(int i=hed[now];i;i=e[i].nxt){
if(vis[e[i].r])continue;
if(e[i].v+G<f[e[i].r]||f[e[i].r]==-1){
f[e[i].r]=e[i].v+G;
Q.push(make_pair(f[e[i].r],e[i].r) );
}
}
}
}
int main(){
int u,v,w;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
}
for(int i=1;i<=n;i++)f[i]=-1;
f[1]=0;
int ans=-1;
spfa();
if(f[n]<ans||ans==-1)ans=f[n];
for(int j=1;j<=k;j++){
for(int i=1;i<=n;i++){
d[i]=f[i];
f[i]=-1;
}
for(int i=1;i<=n;i++){
if(!~d[i])continue;
for(int l=hed[i];l;l=e[l].nxt)
if( (d[i]<f[e[l].r]) || (!~f[e[l].r]) )
f[e[l].r]=d[i];
}
spfa();
if(f[n]<ans||ans==-1)ans=f[n];
}
printf("%d\n",ans);
return 0;
}
This passage is made by Iscream-2001.