goohij   1년 전

출력초과의 원인을 전혀 모르겠어요 ... 도와주세요 

leehosu01   1주 전

if (dist[1] <= 0)
{
printf("-1\n");
}

만으로 -1 처리하지 말고 
int t=n*m;
while()
{
    if(!t--)
{
printf("-1");
return 0;
}
~
~
~
}
를 해서 루프 제한을 걸어보세요

leehosu01   1주 전

그리고

if (dist[1] < 0)
{
printf("-1\n");
}

입니다

leehosu01   1주 전

while (!q.empty())
{
int from = q.front(); q.pop();
visit[from] = 0;

고치세요

leehosu01   1주 전

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 98765432
int dist[501];
int path[501];
int visit[501];
int main()
{
int n, m;
scanf("%d %d", &n, &m);

vector<pair<int, int> > vec[501];
for (int i = 0; i < m; i++)
{
int v1, v2, val;
scanf("%d %d %d", &v1, &v2, &val);

vec[v1].push_back({ v2, val });
}

for (int i = 1; i <= n; i++)
dist[i] = INF;

queue<int> q;
dist[1] = 0;
q.push(1);
visit[1] = 1;
int t=n*m;
while (!q.empty())
{
int from = q.front(); q.pop();
visit[from] = 0;
    if(!t--)
{
printf("-1");
return 0;
}

for (int i = 0; i < vec[from].size(); i++)
{
int to = vec[from][i].first;
int cost = vec[from][i].second;

if (dist[to] > dist[from] + cost)
{
dist[to] = dist[from] + cost;
if (visit[to] == 0)
{
q.push(to);
visit[to] = 1;
}
}
}
}

if (dist[1] < 0)
{
printf("-1\n");
}
else {
for (int i = 2; i <= n; i++)
{
if (dist[i] == INF)
printf("-1\n");
else
printf("%d\n", dist[i]);
}
}
return 0;
}

댓글을 작성하려면 로그인해야 합니다.