백준(BOJ) 15808 주말 여행 계획 **

# 다익스트라 알고리즘

# 실수 했던 점

기본적으로 다익스트라 알고리즘은 각 방문지의 값을 INF로 초기화 시켜놔야 하는데

초기화를 안했다.

이문제의 경우 -INF로 해야한다

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <utility>
#include <climits>
#include <functional>
#define MAX 1005
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

int n,a,b,c,d;
int arr[MAX][MAX],djk[MAX];
bool tf[MAX];
vector<pi> v;

int find_next()
{
    int ret=-1,val=-INF;
    for(int i=1;i<=n;i++)
        if(tf[i]==false&&djk[i]>val)
        {
            val=djk[i];
            ret=i;
        }
    return ret;
}

int main() {
    fill_n(&djk[0],MAX,-INF);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&arr[i][j]);
    scanf("%d%d",&a,&b);
    for(int i=0;i<a;i++)
    {
        scanf("%d%d",&c,&d);
        djk[c]=d;
    }
    for(int i=0;i<b;i++)
    {
        scanf("%d%d",&c,&d);
        v.push_back(make_pair(c, d));
    }
    int tmp=find_next();
    while(tmp!=-1)
    {
        tf[tmp]=true;
        for(int i=1;i<=n;i++)
            if(arr[tmp][i]!=0&&djk[i]<djk[tmp]-arr[tmp][i])
                djk[i]=djk[tmp]-arr[tmp][i];
        tmp=find_next();
    }
    int ans=-INF;
    for(int i=0;i<v.size();i++)
        if(ans<djk[v[i].first]+v[i].second)
            ans=djk[v[i].first]+v[i].second;
    printf("%d",ans);
    return 0;
}