2160 农场派对

Hank · 发表于 2021-6-14 09:39:10

1 + 2 = 3
2 + 3 = 11
3 + 3 = 12
1 + 3 + 3 = 13

Hank · 发表于 2021-6-14 10:20:08

First:2160
首先，我们要读题：
N（1≤N≤1000）头牛要去参加一场在编号为x（1≤x≤N）的牛的农场举行的派对。有M（1≤M≤100000）条有向道路，每条路长Ti（1≤Ti≤100）；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这N头牛的最短路径（一个来回）中最长的一条的长度。特别提醒：可能有权值不同的重边
喔，一看，模板题！
但是，这题有一个大坑点：
有向道路
也就是说，去时的路不一定是回来的路

Second:举例

如上图，假如说所有人都到3去
那2号就直接去了，但回不来了
So,这道题需要两次DJI
一次是所有点到s的距离，一次是s到所有点的距离

Third：code

/*
ID: jian8281
TASK: test
LANG: C++
*/
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<iostream>
using namespace std;
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define MAXN 100010
int n, m, s, ans = -2147483647;
int total1, head1[MAXN], to1[MAXN], nxt1[MAXN], val1[MAXN];
int total2, head2[MAXN], to2[MAXN], nxt2[MAXN], val2[MAXN];
int dis1[MAXN];
bool vis1[MAXN];
int dis2[MAXN];
bool vis2[MAXN];
struct node
{
int a;
int b;
};
priority_queue<node> q;
bool operator < (node x,node y
){
return x.b > y.b;
}
void aadd(int a, int b, int c)
{
total1++;
to1[total1] = b;
val1[total1] = c;
nxt1[total1] = head1[a];
head1[a] = total1;
return;
}
void addd(int a,int b,int c)
{
total2++;
to2[total2] = b;
val2[total2] = c;
nxt2[total2] = head2[a];
head2[a] = total2;
return;
}
void dijkstra1()
{
dis1[s] = 0;
q.push(node{s, 0});
while(!q.empty())
{
int u = q.top().a;
q.pop();
if(vis1[u])
{
continue;
}
vis1[u] = true;
for(int e = head1[u];e;e = nxt1[e])
{
if(dis1[to1[e]] > dis1[u] + val1[e])
{
dis1[to1[e]] = dis1[u] + val1[e];
q.push(node{to1[e], dis1[to1[e]]});
}
}
}
return;
}
void dijkstra2()
{
dis2[s] = 0;
q.push(node{s, 0});
while(!q.empty())
{
int u = q.top().a;
q.pop();
if(vis2[u])
{
continue;
}
vis2[u] = true;
for(int e = head2[u];e;e = nxt2[e])
{
if(dis2[to2[e]] > dis2[u] + val2[e])
{
dis2[to2[e]] = dis2[u] + val2[e];
q.push(node{to2[e], dis2[to2[e]]});
}
}
}
return;
}
int main()
{
cin >> n >> m >> s;
int a, b, c;
for(int i = 1;i <= m;++i)
{
cin>> a >> b >> c;
aadd(a, b, c);
addd(b, a, c);
}
for(int i = 1;i <= n;++i)
{
dis1[i] = dis2[i] = 2147483647;
}
dijkstra1();
dijkstra2();
for(int i = 1;i <= n;++i)
{
ans = max(ans, dis1[i] + dis2[i]);
}
cout << ans;
}

复制代码

caidan

1.0亿

2160 农场派对

本帖子中包含更多资源