HDU 2066 한 사람의 여행 (dijk 최 단 길)
자 기 는 정말 약 하 다.난이도 가 1 성 밖 에 안 되 는 템 플 릿 문 제 를 한동안 생각 했다.다 원 인 줄 알 았 는데 플 로 디 알고리즘 으로 더 잘 만 들 었 는데 1000 ^ 3 의 플 로 디 는 분명히 시간 을 초과 할 것 이다.그래서 플 로 디 알고리즘 을 어떻게 바 꾸 려 고 했 어 요.나중에 갑자기 단원 으로 하 는 게 오히려 시간 을 초과 하지 않 는 다 는 생각 이 들 어서...아 이 큐 가 급 해.그래서 디 제 스 트 라 알고리즘 으로 만 들 었 어 요.
코드 는 다음 과 같 습 니 다:
#include <stdio.h>
#include <string.h>
int n, m, map[1002][1002], d[1002], vis[1002], maxint=1000000, nn;
void dijk(int s)
{
int i,j, min1,pos;
for(i=1;i<=nn;i++)
d[i]=map[s][i];
vis[s]=1;
d[s]=0;
for(i=1;i<nn;i++)
{
min1=maxint;
for(j=1;j<=nn;j++)
{
if(!vis[j]&&min1>d[j])
{
min1=d[j];
pos=j;
}
}
vis[pos]=1;
for(j=1;j<=nn;j++)
{
if(d[j]>map[pos][j]+d[pos])
d[j]=map[pos][j]+d[pos];
}
}
}
int main()
{
int t, a, b, c, p[1000],q[1000], min1, min2, s, i, j;
while(scanf("%d%d%d",&t,&n,&m)!=EOF)
{
min2=maxint;
nn=0;
for(i=0;i<=1001;i++)
{
for(j=0;j<=1001;j++)
{
map[i][j]=maxint;
}
}
while(t--)
{
scanf("%d%d%d",&a,&b,&c);
if(nn<a)
nn=a;
if(nn<b)
nn=b;
if(map[a][b]>c)
{
map[a][b]=map[b][a]=c;
}
}
for(i=0;i<n;i++)
scanf("%d",&p[i]);
for(i=0;i<m;i++)
scanf("%d",&q[i]);
for(i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
dijk(p[i]);
min1=maxint;
for(j=0;j<m;j++)
{
if(min1>d[q[j]])
min1=d[q[j]];
}
if(min2>min1)
min2=min1;
}
printf("%d
",min2);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.