【图论】最短路应用
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