hdu 2544 최 단 로(두 점 사이 최 단 경로)
11227 단어 최 단 경로
방법 1:dijkstra 알고리즘,두 점 사이 의 가장 짧 은 경 로 를 구 합 니 다.
/************************************************************************/
/*
hdu
:dijkstra 。
*/
/************************************************************************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define MAX 0xfffffff
const int N = 101;
int map[N][N];
int vis[N];
int dj[N];
int num,m,n;
void build_map()
{
int a,b,c;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
map[i][j] = map[j][i] = (i==j)?0:MAX;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b] = map[b][a] = c;
}
}
int DJ()
{
int t = n;
int sum = 0;
int min,k;
for (int i = 1; i <= n; i++)
dj[i] = MAX;
int cur = 1;
dj[cur] = 0;
while(1)
{
min = MAX;
vis[cur] = 1;
for (int i = 1; i <= n; i++)
{
if(vis[i]==1)continue;
if(dj[i]>map[i][cur]+dj[cur])
dj[i] = map[i][cur]+dj[cur];
if (dj[i]<min)
{
min = dj[i];
k = i;
}
}
cur = k;
if(k==n)break;
}
return dj[n];
}
int main()
{
while(scanf("%d%d",&n,&m) && (n!=0 && m!=0) )
{
build_map();
memset(vis,0,sizeof(vis));
printf("%d
",DJ());
}
return 0;
}
방법 2:floyd 알고리즘,두 점 사이 의 최 단 거 리 를 구하 십시오.distance[i][j]=min(distance[i][j],distance[i][k]+distance[k][j]);중간 점 을 빌리다.
/************************************************************************/
/*
hdu
:floyd , ,(u,v) = min( (u,v),(v,w)+(w,v) );
*/
/************************************************************************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define MIN(a,b) a<b?a:b
#define MAX 0xfffffff
const int N = 101;
int map[N][N];
int vis[N];
int dj[N];
int num,m,n;
void build_map()
{
int a,b,c;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
map[i][j] = map[j][i] = (i==j)?0:MAX;
for (int i = 0; i < m; i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b] = map[b][a] = c;
}
}
int floyd()
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
map[i][j] = MIN(map[i][j],map[i][k] + map[k][j]);
}
return map[1][n];
}
int main()
{
while(scanf("%d%d",&n,&m) && (n!=0 && m!=0) )
{
build_map();
memset(vis,0,sizeof(vis));
printf("%d
",floyd());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
7 - 26 해리 포 터 스 시험 (25 점) (Floyd 알고리즘)In Professor McGonagall's class of Transfiguration, Harry Potter is learning how to transform one object into another by...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.