HDU-1874-원활한 엔지니어링
Status
Practice
HDU 1874 Description의 한 성은 여러 해 동안 원활한 공사 계획을 실행한 후에 마침내 많은 길을 건설했다.길을 많이 걷지 않아도 좋지 않다. 매번 한 도시에서 다른 도시로 갈 때마다 많은 도로 방안을 선택할 수 있지만 어떤 방안은 다른 방안보다 걷는 거리가 훨씬 짧다.이것은 행인들을 매우 괴롭힌다.
지금, 이미 기점과 종점을 알고 있으니, 기점에서 종점까지 가장 짧게 걸어야 할 거리가 얼마나 되는지 계산해 보세요.
Input 이 제목에는 여러 개의 데이터가 포함되어 있습니다. 파일이 끝날 때까지 처리하십시오.각 그룹의 데이터 첫 줄은 두 개의 정수 N과 M(0
Sample Input 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2
Sample Output 2 - 1 템플릿 문제, 나 같은 어제 가장 짧은 길을 배운 사람에게 이때 마음은 활기차다. 그래서 좋은 날은 두 가지 방법으로 쓰기로 결정했다.
갱점, 이것은 무방향도이고 두 점 사이에 여러 번의 경로를 제시할 수 있다. 행렬에 저장할 때 판단해야 한다. 두 점 사이의 최단로 프로이드 알고리즘만 저장한다.
#include<stdio.h>
#include<string.h>
#include<string>
#include<stack>
#include<queue>
#include<math.h>
#include<limits.h>
#include<iostream>
#include<algorithm>
using namespace std;
//
int map[205][205];//
const int inf=100000000;//
int N;//
int M;//
int a,b,c;//a b c
int s,t;//
int main()
{
while(scanf("%d%d",&N,&M)!=EOF)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
if(i==j)
map[i][j]=0;
else
map[i][j]=inf;// -1， inf
}
}
for(int i=1; i<=M; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c<map[a][b])
{
map[a][b]=c;
map[b][a]=c;//
}
}
for(int k=0; k<N; k++)
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
scanf("%d%d",&s,&t);
printf("%d
",map[s][t]!=inf?map[s][t]:-1);
}
return 0;
}
디제스트라 알고리즘
#include<stdio.h>
#include<string.h>
#include<string>
#include<stack>
#include<queue>
#include<math.h>
#include<limits.h>
#include<iostream>
#include<algorithm>
using namespace std;
//
int map[205][205];//
int dis[205];//
int visited[205];// 1， 0
int N;//
int M;//
int a,b,c;//a b b a c
int s,t;//s t
int u,v,minn;//
const int inf=100000000;
int main()
{
while(scanf("%d%d",&N,&M)!=EOF)
{
for(int i=0; i<N; i++) //
{
for(int j=0; j<N; j++)
{
if(i==j)
map[i][j]=0;
else
map[i][j]=inf;
}
}
for(int i=0; i<M; i++) // M
{
scanf("%d%d%d",&a,&b,&c);
if(c<map[a][b])
{
map[a][b]=c;//
map[b][a]=c;
}
}
scanf("%d%d",&s,&t);
memset(visited,0,sizeof(visited));
visited[s]=1;
for(int i=0; i<N; i++)
dis[i]=map[s][i];// dis
for(int i=0; i<N-1; i++) //
{
minn=inf;
for(int j=0; j<N; j++)
{
if(visited[j]==0&&dis[j]<minn)
{
minn=dis[j];
u=j;
}
}
visited[u]=1;//
for(v=0; v<N; v++) //
{
if(map[u][v]<inf)
{
if(dis[v]>dis[u]+map[u][v])
{
dis[v]=dis[u]+map[u][v];
}
}
}
}
printf("%d
",dis[t]==inf?-1:dis[t]);
}
return 0;
}
완선한 것은 아니다. 왜냐하면 인접 시계 더미로 최적화할 수 있기 때문이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS)알고리즘 유형 : 다익스트라 or BFS 다익스트라 풀이 BFS 풀이 SOLVE 1) 풀이 요약 (다익스트라 풀이) 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다. 가중치가 모두 0 또는 양수이고, 특정...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
