hdu 3790 최 단 경로 문제 (거리 와 비용)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19009 Accepted Submission(s): 5667
Problem Description
n 개의 점 을 드 리 겠 습 니 다. m 개의 방향 이 없고 모든 변 에 길이 d 와 소비 p 가 있 습 니 다. 출발점 s 종점 t 를 드 리 겠 습 니 다. 출력 출발점 에서 종점 까지 의 최 단 거리 와 비용 을 요구 합 니 다. 만약 에 최 단 거리 에 여러 노선 이 있 으 면 수출 비용 이 가장 적 습 니 다.
Input
n, m 를 입력 하 십시오. 점 의 번 호 는 1 ~ n 이 고 그 다음 에 m 줄 입 니 다. 줄 마다 4 개의 숫자 a, b, d, p 는 a 와 b 사이 에 한 변 이 있 고 그 길 이 는 d 이 며 비용 은 p 입 니 다.마지막 줄 은 두 개의 수 s, t 이다.기점 s, 종점.n 과 m 가 0 일 때 입력 이 끝 납 니 다.(1
Output
한 줄 을 출력 하 는 데 는 두 개의 수가 있 는데, 가장 짧 은 거리 와 비용 이 든다.
Sample Input
3 2 1 2 5 6 2 3 4 5 1 3 0 0
Sample Output
9 11
문제 풀이 방향: 먼저 내 가 이 문 제 를 푸 는 느낌 을 나타 낸다. 니 마, 밥 도 안 먹 었 어.처음에 보 았 을 때 생각 이 좀 떠 올 라 서 하기 시 작 했 습 니 다. 시간 이 지나 면 코드 를 쓴 셈 입 니 다. 문제 에서 준 테스트 데이터 도 맞 았 고 결 과 는 제출 하 자마자 틀 렸 습 니 다.답답 해 ~ ~ 이 어 오 류 를 찾기 시작 해 한참 을 찾 았 다.그러나 이 문 제 는 디 제 스 트 라 가 가장 짧 은 길 을 찾 는 과정 에서 주의해 야 한다. 출발점 에서 다음 에 거 쳐 야 할 점 까지 의 거 리 는 같다. 즉, 다음 점 까지 여러 가지 만족 조건 이 있 을 수 있 고 이런 점 에 대해 일일이 처리 해 야 한다. 구체 적 인 해석 코드 에서 준 것 이 있다.정확하게 제출 한 후에 이 문 제 를 생각해 보 는 것 은 확실히 어렵 지 않 고 어 려 우 면 세부 적 으로 처리 하기 어렵다.그래서 디 테 일이 성 패 를 결정 하 는 거 야!!
코드 마지막 에 저 는 세 조 의 테스트 데 이 터 를 제 시 했 습 니 다. 이 세 조 의 데이터 테스트 결과 가 문제 가 없다 면 제출 하 는 것 도 문제 가 없 을 것 입 니 다.
：
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
#define Min(a,b) a>b?b:a
struct Node
{
int adj,val;
}g[1005][1005];
int dist[1005];//
int value[1005];//
int used[1005];//
int n,m,i,j;
void Dijkstra(int s)
{
memset(dist,0x3f,sizeof(dist));
memset(value,0x3f,sizeof(value));
memset(used,0,sizeof(used));
dist[s]=0;//
value[s]=0;
while(1)
{
int k,u=-1,d[1005];
int min=INF;
memset(d,0,sizeof(d));
for(i=1;i<=n;i++)
if(used[i]==0&&dist[i]<min)//
{
min=dist[i];
u=i;//
}
if(u==-1)//
return ;
for(i=1,k=0;i<=n;i++)
if(dist[u]==dist[i]&&used[i]==0)
d[k++]=i;//
for(i=0;i<k;i++)
used[d[i]]=1;
for(i=0;i<k;i++)//
for(j=1;j<=n;j++)
if(g[d[i]][j].adj!=INF && (dist[d[i]]+g[d[i]][j].adj)<=dist[j])
{// main()
if((dist[d[i]]+g[d[i]][j].adj)<dist[j])
value[j]=value[d[i]]+g[d[i]][j].val;
else
value[j]=Min(value[j],value[d[i]]+g[d[i]][j].val);
dist[j]=dist[d[i]]+g[d[i]][j].adj;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m) && (n||m))
{
int a,b,d,p;
memset(g,0x3f,sizeof(g));
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&d,&p);
if(d<=g[a][b].adj)//
{
if(d==g[a][b].adj)// ，
g[a][b].val=g[b][a].val=Min(p,g[a][b].val);
else// ，
g[a][b].val=g[b][a].val=p;
g[a][b].adj=g[b][a].adj=d;//
}
}
int s,t;
scanf("%d%d",&s,&t);
Dijkstra(s);
printf("%d %d
",dist[t],value[t]);
}
return 0;
}
/*
//
2 2
1 2 5 10
2 1 4 12
1 2
4 12
4 4
1 2 5 6
2 3 4 5
1 4 5 10
4 3 4 2
1 3
9 11
6 7
1 2 5 6
1 3 5 1
2 6 2 1
3 4 1 1
4 2 1 1
4 5 1 1
5 2 3 1
5 6
4 3
*/
//
// for(i=1;i<=n;i++)
// {
// for(j=1;j<=n;j++)
// {
// if(g[i][j].adj==INF)
// printf("%d/%d ",0,0);
// else
// printf("%d/%d ",g[i][j]);
// }
// printf("
");
// }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
