【洛谷】P1821 [USACO07FEB] Cow Party S(单源最短路)
程序员文章站
2022-07-13 11:29:31
...
题目描述
寒假到了,头牛都要去参加一场在编号为 的牛的农场举行的派对,农场之间有 条有向路,每条路都有一定的长度。
每头牛参加完派对后都必须回家,无论是去参加派对还是回家,每头牛都会选择最短路径,求这 头牛的最短路径(一个来回)中最长的一条路径长度。
输入格式
第一行有三个整数,分别表示牛的数量 ,道路数和派对农场编号 。
接下来 行,每行三个整数 ,,表示存在一条由 通向 的长度为 的道路。
输出格式
输出一行一个整数表示答案。
输入样例
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
输出样例
10
说明/提示
样例 1 解释
数据规模与约定
对于全部的测试点,保证 , ,,,保证从任何一个结点出发都能到达 号结点,且从 出发可以到达其他所有节点。
spfa70分代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+50;
const int maxm=1e5+50;
const int INF=0x3f3f3f3f;
struct edge{
int u;
int v;
int w;
int next;
}e1[maxm],e2[maxn];
int head1[maxn],dis1[maxn],inq1[maxn],cnt1=0;
int head2[maxn],dis2[maxn],inq2[maxn],cnt2=0;
void add1(int u,int v,int w){
cnt1++;
e1[cnt1].u=u;
e1[cnt1].v=v;
e1[cnt1].w=w;
e1[cnt1].next=head1[u];
head1[u]=cnt1;
}
void add2(int u,int v,int w){
cnt2++;
e2[cnt2].u=u;
e2[cnt2].v=v;
e2[cnt2].w=w;
e2[cnt2].next=head2[u];
head2[u]=cnt2;
}
int n,m,x;
void spfa1(int s){
memset(dis1, INF, sizeof(dis1));
queue<int>q;
q.push(s);
dis1[s]=0;
inq1[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inq1[u]=0;
for(int i=head1[u];i>0;i=e1[i].next){
int v=e1[i].v;
int w=e1[i].w;
if(dis1[v]>dis1[u]+w){
dis1[v]=dis1[u]+w;
if(!inq1[v]){
q.push(v);
inq1[v]=1;
}
}
}
}
}
void spfa2(int s){
memset(dis2, INF, sizeof(dis2));
queue<int>q;
q.push(s);
dis2[s]=0;
inq2[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
inq2[u]=0;
for(int i=head2[u];i>0;i=e2[i].next){
int v=e2[i].v;
int w=e2[i].w;
if(dis2[v]>dis2[u]+w){
dis2[v]=dis2[u]+w;
if(!inq2[v]){
q.push(v);
inq2[v]=1;
}
}
}
}
}
int main(){
// freopen("inn.txt","r",stdin);
//freopen("outt.txt","w",stdout);
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add1(u,v,w);
add2(v,u,w);
}
spfa1(x);
spfa2(x);
int ans=-1;
for(int i=1;i<=n;i++)
ans= max(ans,dis1[i]+dis2[i]);
printf("%d\n",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}
spfa双端队列优化70分代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+50;
const int maxm=1e5+50;
const int INF=0x3f3f3f3f;
struct edge{
int u;
int v;
int w;
int next;
}e1[maxm],e2[maxn];
int head1[maxn],dis1[maxn],inq1[maxn],cnt1=0;
int head2[maxn],dis2[maxn],inq2[maxn],cnt2=0;
void add1(int u,int v,int w){
cnt1++;
e1[cnt1].u=u;
e1[cnt1].v=v;
e1[cnt1].w=w;
e1[cnt1].next=head1[u];
head1[u]=cnt1;
}
void add2(int u,int v,int w){
cnt2++;
e2[cnt2].u=u;
e2[cnt2].v=v;
e2[cnt2].w=w;
e2[cnt2].next=head2[u];
head2[u]=cnt2;
}
int n,m,x;
void spfa1(int s){
memset(dis1, INF, sizeof(dis1));
deque<int>q;
q.push_back(s);
dis1[s]=0;
inq1[s]=1;
while(!q.empty()){
int u=q.front();
q.pop_front();
inq1[u]=0;
for(int i=head1[u];i>0;i=e1[i].next){
int v=e1[i].v;
int w=e1[i].w;
if(dis1[v]>dis1[u]+w){
dis1[v]=dis1[u]+w;
if(!inq1[v]){
inq1[v]=1;
if(!q.empty()&&dis1[v]<=dis1[q.front()])
q.push_front(v);
else q.push_back(v);
}
}
}
}
}
void spfa2(int s){
memset(dis2, INF, sizeof(dis2));
deque<int>q;
q.push_back(s);
dis2[s]=0;
inq2[s]=1;
while(!q.empty()){
int u=q.front();
q.pop_front();
inq2[u]=0;
for(int i=head2[u];i>0;i=e2[i].next){
int v=e2[i].v;
int w=e2[i].w;
if(dis2[v]>dis2[u]+w){
dis2[v]=dis2[u]+w;
if(!inq2[v]){
inq2[v]=1;
if(!q.empty()&&dis1[v]<=dis1[q.front()])
q.push_front(v);
else q.push_back(v);
}
}
}
}
}
int main(){
// freopen("inn.txt","r",stdin);
//freopen("outt.txt","w",stdout);
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add1(u,v,w);
add2(v,u,w);
}
spfa1(x);
spfa2(x);
int ans=-1;
for(int i=1;i<=n;i++)
ans= max(ans,dis1[i]+dis2[i]);
printf("%d\n",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}
dijkstra解法AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+50;
const int maxm=1e5+50;
const int inf=0x3f3f3f3f;
struct edge{
int u;
int v;
int w;
int next;
}e1[maxm],e2[maxm];
int head1[maxn],dis1[maxn],cnt1=0;
int head2[maxn],dis2[maxn],cnt2=0;
void add1(int u,int v,int w){
cnt1++;
e1[cnt1].u=u;
e1[cnt1].v=v;
e1[cnt1].w=w;
e1[cnt1].next=head1[u];
head1[u]=cnt1;
}
void add2(int u,int v,int w){
cnt2++;
e2[cnt2].u=u;
e2[cnt2].v=v;
e2[cnt2].w=w;
e2[cnt2].next=head2[u];
head2[u]=cnt2;
}
struct node{
int u,dis;
bool operator<(const node& b) const{
return dis>b.dis;
}
};
int n,m,x;
void disjkstra1(int s){
for(int i=1;i<=n;i++){
dis1[i]=inf;
}
priority_queue<node>que;
dis1[s]=0;
que.push((node){s,dis1[s]});
while(!que.empty()){
node now=que.top();
que.pop();
int u=now.u;
if(now.dis!=dis1[u]) continue;
for(int i=head1[u];i>0;i=e1[i].next){
int v=e1[i].v;
int w=e1[i].w;
if(dis1[v]>dis1[u]+w){
dis1[v]=dis1[u]+w;
que.push((node){v,dis1[v]});
}
}
}
}
void disjkstra2(int s){
for(int i=1;i<=n;i++){
dis2[i]=inf;
}
priority_queue<node>que;
dis2[s]=0;
que.push((node){s,dis2[s]});
while(!que.empty()){
node now=que.top();
que.pop();
int u=now.u;
if(now.dis!=dis2[u]) continue;
for(int i=head2[u];i>0;i=e2[i].next){
int v=e2[i].v;
int w=e2[i].w;
if(dis2[v]>dis2[u]+w){
dis2[v]=dis2[u]+w;
que.push((node){v,dis2[v]});
}
}
}
}
int main(){
//freopen("inn.txt","r",stdin);
//freopen("outt.txt","w",stdout);
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add1(u,v,w);
add2(v,u,w);
}
disjkstra1(x);
disjkstra2(x);
int ans=-1;
for(int i=1;i<=n;i++)
ans= max(ans,dis1[i]+dis2[i]);
printf("%d\n",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}
上一篇: 最短路 Silver Cow Party
下一篇: kuangbin专题之最小生成树