Poj 1985 Cow Marathon (나무의 지름
Description
After hearing about the epidemic of obesity in the USA, Farmer John wants his cows to get more exercise, so he has committed to create a bovine marathon for his cows to run. The marathon route will include a pair of farms and a path comprised of a sequence of roads between them. Since FJ wants the cows to get as much exercise as possible he wants to find the two farms on his map that are the farthest apart from each other (distance being measured in terms of total length of road on the path between the two farms). Help him determine the distances between this farthest pair of farms. Input
Input
Output
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
Sample Output
52
Hint
The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.
제목
N 개의 점 M 개의 변 은 모든 변 에 가중치 가 있 습 니 다. 두 가 지 를 찾 아 이 두 점 사이 의 모든 변 의 가중치 와 가장 길 게 합 니 다.
문제 풀이:
누 드 트 리 의 직경 ZZ 는 뒤에 있 는 방향 을 반나절 동안 고 민 했 습 니 다. 사실 TAT vector 저장 도 를 사용 하지 않 아 도 정말 편리 합 니 다. 하하 하 \ # \ # AC 코드
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
#define CLR(a, b) memset(a, (b), sizeof(a))
const int N = 5e5;
struct node {
int t, val;
};
vector v[N];
bool vis[N];
int dis[N];
int ans, res;
void bfs(int x)
{
CLR(dis,0);
CLR(vis,false);
res = 0;
queue<int> q;
q.push(x);
vis[x] = true;
while(!q.empty()) {
int p = q.front();
q.pop();
if(dis[p] > ans) {
ans = dis[p];
res = p;
}
for(int i = 0;i < v[p].size(); i++) {
node x = v[p][i];
if(!vis[x.t]) {
vis[x.t] = true;
dis[x.t] = dis[p] + x.val;
q.push(x.t);
}
}
}
}
int main()
{
//ios::sync_with_stdio(false);
int n, m;
while(~scanf("%d%d",&n,&m)) {
for(int i = 0; i<= n; i++) v[i].clear();
int x, y, z; char c;
for(int i = 0;i < m; i++) {
scanf("%d%d%d %c",&x,&y,&z,&c);
v[x].push_back((node){y,z});
v[y].push_back((node){x,z});
}
ans = 0;
bfs(1);
ans = 0;
bfs(res);
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
AZ-900을 자택 수험으로 무료 취득한 이야기 (2020/10)에서 2일간(오전중에만)의 온라인 트레이닝을 받는 것으로 무료 바우처를 받을 수 있다(등록 메일에 온다) 때문에, 부터 Peason VUE でスケジュール 버튼을 눌러, 화면에 따라 예약해 합격합시다 . ※2020/1...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.