题意:给定\(n(n<=1000)\)个点\(p(p<=10000)\)条边的无向图,允许把k条边的权值变为0,找到一条从1到n的路径,使得路径上的权值最大的边最小.
分析:
方法一:"最大的边最小"???直接上二分答案.每次二分的值为\(mid\),然后把权值大于\(mid\)的边视为边权为1,小于等于\(mid\)的边视为边权为0,对于边权只有0和1的图,我们可以跑双端队列BFS(建立一个双端队列,如果当前节点v是由边权为0的边得到的,就从队头入队,否则从队尾入队),每次判定\(dis[n]\)是否小于等于\(k\)即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1005;
const int M=20005;
int n,p,k,ans=-1,dis[N];
int tot,head[N],nxt[M],to[M],w[M];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
inline bool check(int mid){
memset(dis,0x3f,sizeof(dis));
deque<int>q;q.clear();
q.push_back(1);dis[1]=0;
while(q.size()){
int u=q.front();q.pop_front();
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(w[i]>mid){
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
q.push_back(v);
if(v==n&&dis[v]<=k)return true;
}
}
if(w[i]<=mid){
if(dis[v]>dis[u]){
dis[v]=dis[u];
q.push_front(v);
if(v==n&&dis[v]<=k)return true;
}
}
}
}
return false;
}
int main(){
n=read(),p=read(),k=read();int l=0,r=0;
for(int i=1;i<=p;++i){
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,c);r=max(r,c);
}
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(ans==-1)puts("-1");
else printf("%d\n",ans);
return 0;
}
方法二:分层图.建立k层,不同层之间的边的边权为0,同一层的边的边权不变,直接在分层图上跑最短路即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=100005;
const int M=1000005;
int n,m,k,ans,dis[N],visit[N];
int tot,head[N],to[M],nxt[M],w[M];
inline void add(int a,int b,int c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
struct node{
int id,val;
bool operator <(const node &x)const{
return val>x.val;
}
}temp;
priority_queue<node>q;
inline void dij(){
memset(dis,0x3f,sizeof(dis));dis[1]=0;
temp.id=1;temp.val=0;q.push(temp);
while(q.size()){
temp=q.top();q.pop();
int u=temp.id;
if(visit[u])continue;
visit[u]=1;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]>max(dis[u],w[i])){
dis[v]=max(dis[u],w[i]);
temp.id=v;temp.val=dis[v];q.push(temp);
}
}
}
}
int main(){
n=read();m=read();k=read();
for(int i=1;i<=m;++i){
int a=read(),b=read(),c=read();
add(a,b,c);add(b,a,c);
for(int j=1;j<=k;++j){//建立分层图
add(a+j*n,b+j*n,c);
add(b+j*n,a+j*n,c);
add(a+j*n-n,b+j*n,0);
add(b+j*n-n,a+j*n,0);
}
}
dij();ans=1e9;
for(int j=0;j<=k;++j)
ans=min(ans,dis[n+j*n]);//每一层的n节点都可能是答案
if(ans==1e9)puts("-1");
else printf("%d\n",ans);
return 0;
}