[BOJ 1504] int 범위 초과 유의하기

path1,2를 구할때 뿐만아니라, d배열또한 int범위를 넓혀야 한다.

	#include <cstdio>
	#include <queue>
	#include <list>
	#include <stack>
	#define SIZE 801
	#define INF 987654321
	using namespace std;
	typedef struct Node
	{
	int vertex;
	int edge;
	Node(int v,int e):vertex(v),edge(e){}
	}Node;
	struct cmp{
	bool operator()(Node a, Node b){
	return a.edge > b.edge;
	}
	};
	list<Node> li[SIZE];
	long long d[3][SIZE];
	int num_V,num_E;
	void dijstra(int n,int idx,int start)
	{
	priority_queue<Node,vector<Node>,cmp> pq;
	for (int u = 1; u <= num_V; u++)
	{ d[idx][u] = INF; }
	d[idx][start] = 0;
	pq.push(Node(start,d[idx][start]));
	while(!pq.empty())
	{
	struct Node u = pq.top();
	pq.pop();
	if (u.edge > d[idx][u.vertex])
	continue;
	list<Node> :: iterator temp;
	for (temp = li[u.vertex].begin(); temp != li[u.vertex].end(); temp++)
	{
	if (d[idx][(*temp).vertex] > (*temp).edge + d[idx][u.vertex])
	{
	d[idx][(*temp).vertex] = (*temp).edge + d[idx][u.vertex];
	pq.push(*temp);
	}
	}
	}
	}
	int main(void)
	{
	scanf("%d%d",&num_V,&num_E);
	int temp_V1, temp_V2, tempEdge;
	for (int i = 0; i< num_E; i++)
	{
	scanf("%d%d%d",&temp_V1,&temp_V2,&tempEdge);
	li[temp_V1].push_back(Node(temp_V2,tempEdge));
	li[temp_V2].push_back(Node(temp_V1,tempEdge));
	}
	int n1,n2;
	scanf("%d%d",&n1,&n2);
	dijstra(num_V,0,1);
	dijstra(num_V,1,n1);
	dijstra(num_V,2,n2);
	long long path1,path2;
	path1 = d[0][n1] + d[1][n2] + d[2][num_V];
	path2 = d[0][n2] + d[2][n1] + d[1][num_V];
	long long min;
	if (path1 < path2)
	min = path1;
	else
	min = path2;
	if (min >= INF)
	printf("-1");
	else
	printf("%lld",min);
	}

view raw [BOJ 1504] hosted with ❤ by GitHub