【图论】最短路应用

1135. 新年好

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

MarkDown视图Copy

重庆城里有 nn 个车站，mm 条 双向 公路连接其中的某些车站。

每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。

在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 11，他有五个亲戚，分别住在车站 a,b,c,d,ea,b,c,d,e。

过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。

怎样走，才需要最少的时间？

输入格式

第一行：包含两个整数 n,mn,m，分别表示车站数目和公路数目。

第二行：包含五个整数 a,b,c,d,ea,b,c,d,e，分别表示五个亲戚所在车站编号。

以下 mm 行，每行三个整数 x,y,tx,y,t，表示公路连接的两个车站编号和时间。

输出格式

输出仅一行，包含一个整数 TT，表示最少的总时间。

数据范围

1≤n≤500001≤n≤50000,
1≤m≤1051≤m≤105,
1<a,b,c,d,e≤n1<a,b,c,d,e≤n,
1≤x,y≤n1≤x,y≤n,
1≤t≤1001≤t≤100

输入样例：

Copy

6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7

输出样例：

Copy

21

#include<iostream>
#include<cstring>
#include<queue>
#define pii pair<int,int>
using namespace std;
#define INF 0x3f3f3f3f
const int M=100010;const int N=50010;
struct EDGE{int next;int to;int w;
}edge[2*M];int tot=0;
int n,m;int head[N];
void add(int u,int v,int w){edge[++tot].next=head[u];edge[tot].to=v;edge[tot].w=w;head[u]=tot;
}int ans=INF;
int A[6];
int dis[6][6];
void dijk(int ss){int s=A[ss];int dist[N];bool st[N]={0};memset(dist,INF,sizeof(dist));priority_queue<pii,vector<pii>,greater<pii>>heap;heap.push({0,s});dist[s]=0;while(!heap.empty()){pii temp=heap.top();heap.pop();int x=temp.first;int y=temp.second;if(st[y])continue;st[y]=1;for(int i=head[y];~i;i=edge[i].next){//cout<<"jin"<<endl;int v=edge[i].to;if(dist[v]>x+edge[i].w){dist[v]=x+edge[i].w;heap.push({dist[v],v});}}}for(int i=0;i<=5;i++){dis[ss][i]=dis[i][ss]=dist[A[i]];}
}int B[6];bool book[6];
void dfs(int step){if(step==6){int res=0;//cout<<"B";for(int i=1;i<=5;i++){// 1 2 3 4 5dfs编号//B 亲戚 1 2 3 4 5 编号//A 结点编号//cout<<A[B[i]]<<" ";//cout<<dis[B[i-1]][B[i]]<<" ";res+=dis[B[i-1]][B[i]];}//cout<<res<<endl;ans=min(ans,res);return ;}for(int i=1;i<=5;i++){if(!book[i]){book[i]=1;B[step]=i;dfs(step+1);book[i]=0;}}}int main(){cin>>n>>m;memset(head,-1,sizeof(head));A[0]=1;for(int i=1;i<=5;i++)cin>>A[i];while(m--){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);}for(int i=0;i<=5;i++){dijk(i);}B[0]=0;dfs(1);cout<<ans<<endl;}

 

340. 通信线路

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

MarkDown视图Copy

在郊区有 NN 座通信基站，PP 条 双向 电缆，第 ii 条电缆连接基站 AiAi 和 BiBi。

特别地，11 号基站是通信公司的总站，NN 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 ii 条电缆需要花费 LiLi。

电话公司正在举行优惠活动。

农产主可以指定一条从 11 号基站到 NN 号基站的路径，并指定路径上不超过 KK 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 11 行：三个整数 N，P，KN，P，K。

第 2..P+12..P+1 行：第 i+1i+1 行包含三个整数 Ai,Bi,LiAi,Bi,Li。

输出格式

包含一个整数表示最少花费。

若 11 号基站与 NN 号基站之间不存在路径，则输出 −1−1。

数据范围

0≤K<N≤10000≤K<N≤1000,
1≤P≤100001≤P≤10000,
1≤Li≤10000001≤Li≤1000000

输入样例：

Copy

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例：

Copy

4

难度：中等

时/空限制：1s / 64MB

总通过数：14023

总尝试数：27405

来源： 《算法竞赛进阶指南》USACO2008

算法标签

分层图 

#include<iostream>
using namespace std;
#include<cstring>#define ll long long
#define INF 0x3f3f3f3f
#include<queue>
#define pll pair<ll,ll>
ll n,m,k;
const ll M=10010*4*1010;
const ll N=1010*1010;
struct EDGE{ll next;ll to;ll w;
}edge[2*M];
ll head[N];ll tot=0;
void add(ll u,ll v,ll w){
edge[++tot].next=head[u];
edge[tot].to=v;
edge[tot].w=w;
head[u]=tot;
}ll dist[N];bool st[N];
void dijk(ll s){memset(dist,INF,sizeof(dist));priority_queue<pll,vector<pll>,greater<pll>> heap;heap.push({0,s});dist[s]=0;while(!heap.empty()){pll temp=heap.top();heap.pop();ll d=temp.first;ll u=temp.second;if(st[u])continue;st[u]=1;for(ll i=head[u];~i;i=edge[i].next){ll v=edge[i].to;//一个可以被更新dist[v]>//被更新为多少max(d,)if(dist[v]>max(d,edge[i].w)){dist[v]=max(d,edge[i].w);heap.push({dist[v],v});}}}
}int  main(){cin>>n>>m>>k;memset(head,-1,sizeof(head));while(m--){ll u,v,w;cin>>u>>v>>w;for(ll j=1;j<=k;j++){add(u+(j-1)*n,v+j*n,0);add(v+(j-1)*n,u+j*n,0);}for(ll j=0;j<=k;j++){add(u+j*n,v+j*n,w);add(v+j*n,u+j*n,w);}}dijk(1);ll ans=INF;for(ll j=0;j<=k;j++){ans=min(ans,dist[n+j*n]);}cout<<ans;
}

二分+dijk 

#include<iostream>
using namespace std;
#include<queue>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#include<cstring>
const int M=10010;
const int N=1010;
int n,m,k;
struct EDGE{int next;int to;int w;
}edge[2*M];
int head[N];int tot=0;
void add(int u,int v,int w){edge[++tot].next=head[u];edge[tot].to=v;edge[tot].w=w;head[u]=tot;
}bool check(int mid){priority_queue<pii,vector<pii>,greater<pii>> heap;bool st[N]={0};int dist[N];memset(dist,INF,sizeof(dist));heap.push({0,1});dist[1]=0;while(!heap.empty()){pii temp=heap.top();heap.pop();int d=temp.first;int u=temp.second;if(st[u])continue;st[u]=1;for(int i=head[u];~i;i=edge[i].next){int v=edge[i].to;int w=(edge[i].w>mid);if(dist[v]>d+w){dist[v]=d+w;heap.push({dist[v],v});}}}//mid大，比他大的就会少return dist[n]<=k;}int main()
{memset(head,-1,sizeof(head));cin>>n>>m>>k;while(m--){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);}int l=0,r=1e7+10;while(l<r){int mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}if(l==1e7+10)cout<<-1;else cout<<l;
}

 

 

342. 道路与航线

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

MarkDown视图Copy

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 TT 个城镇，编号为 1∼T1∼T。

这些城镇之间通过 RR 条道路 (编号为 11 到 RR) 和 PP 条航线 (编号为 11 到 PP) 连接。

每条道路 ii 或者航线 ii 连接城镇 AiAi 到 BiBi，花费为 CiCi。

对于道路，0≤Ci≤10,0000≤Ci≤10,000;然而航线的花费很神奇，花费 CiCi 可能是负数(−10,000≤Ci≤10,000−10,000≤Ci≤10,000)。

道路是双向的，可以从 AiAi 到 BiBi，也可以从 BiBi 到 AiAi，花费都是 CiCi。

然而航线与之不同，只可以从 AiAi 到 BiBi。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 AiAi 到 BiBi，那么保证不可能通过一些道路和航线从 BiBi 回到 AiAi。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 SS 把奶牛送到每个城镇的最便宜的方案。

输入格式

第一行包含四个整数 T,R,P,ST,R,P,S。

接下来 RR 行，每行包含三个整数（表示一个道路）Ai,Bi,CiAi,Bi,Ci。

接下来 PP 行，每行包含三个整数（表示一条航线）Ai,Bi,CiAi,Bi,Ci。

输出格式

第 1..T1..T 行：第 ii 行输出从 SS 到达城镇 ii 的最小花费，如果不存在，则输出 NO PATH。

数据范围

1≤T≤250001≤T≤25000,
1≤R,P≤500001≤R,P≤50000,
1≤Ai,Bi,S≤T1≤Ai,Bi,S≤T

输入样例：

Copy

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

输出样例：

Copy

NO PATH
NO PATH
5
0
-95
-100