poj 2244 최 단 로 와 poj 1874 원활 한 프로젝트 계속 dijkstra (디 제 스 트 라)

원활 한 공사 계속, 제목 링크, 여 기 를 클릭,
원활 한 공사 가 계속되다.
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 42205 Accepted Submission(s): 15620
Problem Description
모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 선택 할 수 있 고 어떤 방안 은 다른 방안 보다 걷 는 거리 가 훨씬 짧다.이것 은 행인 들 을 매우 곤란 하 게 한다.
지금 은 출발점 과 종점 을 알 고 있 습 니 다. 출발점 에서 종점 까지 가장 짧 은 거 리 를 걸 어야 하 는 지 계산 해 보 세 요.
Input
이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.각 조 의 데이터 첫 줄 은 두 개의 정수 N 과 M (1 < = N ~ 200, 1 < = M ~ 1000) 을 포함 하고 각각 기 존 도시 의 수량 과 이미 건 설 된 도로 의 수량 을 대표 한다.도 시 는 각각 0 ～ N - 1 번호 로 되 어 있다.다음은 M 행 도로 정보.한 줄 에 세 개의 정수 A, B, X (0 < = A, B 는 N, A! = B, X (1 ~ 10000) 가 있 는데 도시 A 와 도시 B 사이 에 X 의 양 방향 도로 가 있다 는 것 을 나타 낸다. 다음 줄 에 두 개의 정수 S, T (0 < = S, T 는 N 보다 작다) 가 있 는데 각각 출발점 과 종점 을 대표 한다.
Output
각 그룹의 데이터 에 대해 서 는 한 줄 에서 걸 어야 할 가장 짧 은 거 리 를 출력 하 십시오. S 에서 T 까지 의 경로 가 존재 하지 않 으 면 출력 - 1.
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//c++
#include//    
#include//malloc
#include
#include
#include//    
#include//  
#include//  
#include//    
#include// 
#include//  
//#include
#include
#include
#define INF 0x3f3f3f
#define inf 10000000
using namespace std;
int map[205][205],dis[205];
int book[205];//     ;
int main()
{
    int n,m,a,b,x,minm,u;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0; i//      ;
            for(int j=0; jif(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=INF;
            }
        for(int i=0; iscanf("%d%d%d",&a,&b,&x);
            if(x<map[a][b])
            {
                map[a][b]=x;//    
                map[b][a]=x;
            }
        }
        scanf("%d%d",&a,&b);// a,b      ;
        for(int i=0; imap[a][i];//         a ;
        memset(book,0,sizeof(book));
        book[a]=1;
        for(int i=0; i1; i++)//        ;
        {
            minm=INF;
            for(int j=0; jif(book[j]==0&&dis[j]1;//  ，    ;
            for(int v=0; v//  
                if(map[u][v]if(dis[v]>dis[u]+map[u][v])
                        dis[v]=dis[u]+map[u][v];
        }
        printf("%d
",dis[b]==INF?-1:dis[b]);
    }
    return 0;
}

또 템 플 릿 문제 인 디 제 스 트 라 와 크게 다 르 지 않다.
poj 1874 문제 링크, 원활 한 공사 계속.
AC 코드:

#include//c++
#include//    
#include//malloc
#include
#include
#include//    
#include//  
#include//  
#include//    
#include// 
#include//  
//#include
#include
#include
#define INF 0x3f3f3f
#define inf 10000000
using namespace std;
int map[205][205],dis[205],book[205];
int main()
{
    int n,m,a,b,x,minm,u;
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        for(int i=0; i//      ;
        {
            for(int j=0; jmap[i][j]=INF;
            map[i][i]=0;
        }
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&x);
            a--;
            b--;
            if(x<map[a][b])
            {
                map[a][b]=x;//    
                map[b][a]=x;
            }
        }
        dis[0]=0;
        for(int i=0; imap[0][i];
        memset(book,0,sizeof(book));
        book[0]=1;
        for(int i=1; ifor(int j=0; jif(!book[j]&&dis[j]1;
            for(int v=0; vif(map[u][v]if(dis[v]>dis[u]+map[u][v]&&!book[v])
                        dis[v]=dis[u]+map[u][v];
        }
        printf("%d
",dis[n-1]==INF?-1:dis[n-1]);
    }
    return 0;
}