HDU 3790 최단 경로 문제(Dijkstra, 가장 짧은 거리와 시간 필요)

제목 주소: 클릭하여 링크 열기
사고방식: 거리를 갱신할 때 시간도 갱신하면 된다. 도론류의 문제의 각종 구덩이를 정리해 보자. 1도면을 작성할 때 단방향도라고 설명하지 않으면 양방향도를 작성한다. 2는 겹칠 가능성이 있다. 예전과 비교하면 3의 시작점과 끝점은 하나의 점일 수 있다. wrong은 무수한 발을 보냈고 자신의 코드를 조금씩 다른 사람의 코드에 끼워 넣었다. 그 결과 변수명을 잘못 써서 2시간 동안 조정했다.다 눈물이야. 그리고 최단길을 구할 때 Dijkstra 알고리즘이 다 실행되어야 해. 왜냐하면 뒤에 추가된 점 하나가 앞에서 구한 가장 짧은 경로를 아직 짧게 업데이트할 수 있기 때문이야. 나는 예전에 종점의 최단길을 알고 바로 퇴출된 Dijkstra 코드를 썼는데 AC를 할 수 있어. 사실 퇴출할 수 없어. 학장의 조언을 통해 그 문제의 종점이 가장 큰 표호였구나.그래서 빠지는 거랑 안 빠지는 거랑 똑같아요.
AC 코드:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

using namespace std;

const int zui = 0x7fffffff;
const int maxn = 1010;
int n,m;
int dist[maxn][maxn],cost[maxn][maxn],visit[maxn];
int lowdist[maxn],lowcost[maxn];
int start,end1;

void Dijkstra()
{
    int i,j,k,min2;
    memset(visit,0,sizeof(visit));
    for(i=1; i<=n; i++)
    {
        lowdist[i] = dist[start][i];
        lowcost[i] = cost[start][i];
    }
    visit[start] = 1;
    for(i=1; i<n; i++)
    {
        min2 = zui;
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && lowdist[j] < min2)
            {
                min2 = lowdist[j];
                k = j;
            }
        }
        visit[k] = 1;
        for(j=1; j<=n; j++)
        {
            if(!visit[j] && dist[k][j] < zui)
            {
                if(lowdist[k] + dist[k][j] < lowdist[j])
                {
                    lowdist[j] = lowdist[k] + dist[k][j];
                    lowcost[j] = lowcost[k] + cost[k][j];
                }
                else if(lowdist[k] + dist[k][j] == lowdist[j])
                {
                    if(lowcost[k] + cost[k][j] < lowcost[j])
                    {
                        lowcost[j] = lowcost[k] + cost[k][j];
                    }
                }
            }
        }
    }
}


int main()
{
    int i,j;
    int a,b,d,p;
    while(scanf("%d%d",&n,&m))
    {
        if(n + m == 0)
            break;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                dist[i][j] = zui;
                cost[i][j] = zui;
            }
        }
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d%d",&a,&b,&d,&p);
            if(d < dist[a][b])
            {
                dist[a][b] = dist[b][a] = d;
                cost[a][b] = cost[b][a] = p;
            }
            else if(d == dist[a][b])
            {
                if(p < cost[a][b])
                {
                    cost[a][b] = cost[b][a] = p;
                }
            }
        }
        scanf("%d%d",&start,&end1);
        Dijkstra();
        printf("%d %d
",lowdist[end1],lowcost[end1]);
    }
    return 0;
}

오류 코드:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

using namespace std;

const int zui = 1000000000;
const int maxn = 1010;
int n,m,start,end1;
int dis[maxn][maxn],cost[maxn][maxn];
int lowcost1[maxn],lowcost2[maxn],visit[maxn];

void Dijkstra()
{
    memset(visit,0,sizeof(visit));
    int i,j,k;
    for(i=1; i<=n; i++)
    {
        lowcost1[i] = dis[start][i];
        lowcost2[i] = cost[start][i];
    }
    visit[start] = 1;
    for(i=1; i<n; i++)
    {
        int min1 = zui - 10;
        for(j=1; j<=n; j++)
        {
            if(visit[j] == 0 && lowcost1[j] <= min1)
            {
                if(lowcost1[j] < min1)
                {
                    min1 = lowcost1[j];
                    k = j;
                }
                else if(lowcost1[j] == min1)
                {
                    if(lowcost2[j] < lowcost2[k])
                    {
                        k = j;
                    }
                }
            }
        }
        visit[k] = 1;
        if(k == end1)
            return;
        for(j=1; j<=n; j++)
        {
            if(visit[j] == 0 && lowcost1[k] + dis[k][j] < lowcost1[j])
            {
                lowcost1[j] = lowcost1[k] + dis[k][j];
                lowcost2[j] = lowcost2[k] + cost[k][j];//        
            }
        }
    }
}

int main()
{
    int i,j;
    int a,b,d,p;
    while(scanf("%d%d",&n,&m))
    {
        if(n + m == 0)
            break;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                dis[i][j] = zui;
                cost[i][j] = zui;
            }
        }
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d%d",&a,&b,&d,&p);
            if(d < dis[a][b])
            {
                dis[a][b] = dis[b][a] = d;
                cost[a][b] = cost[b][a] = p;
            }
            else if(d == dis[a][b])
            {
                if(p < cost[a][b])
                {
                    cost[a][b] = cost[b][a] = p;
                }
            }
        }
        scanf("%d%d",&start,&end1);
        Dijkstra();
        printf("%d %d
",lowcost1[end1],lowcost2[end1]);
    }
    return 0;
}

처음에 생각이 혼란스러웠는데 이 코드를 썼는데 다른 사람의 문제를 보고 알았습니다. 제 생각은 틀렸습니다. 저는 경로가 어렸을 때의 돈만 갱신하고 경로가 같을 때의 돈수는 갱신하지 않았습니다. 그 중에서 경로가 같고 돈수가 가장 낮은 것을 찾았습니다. 저는 구하는 순서가 바뀌었을 뿐 돈의 수를 갱신하지 않았습니다.
Dijkstra 알고리즘에서 j의 for 순환 문장 2개를 i의 순환 문장에 끼워 넣는 것을 기억해라. 처음에는 이것도 틀렸다.