글 읽기 - 시간초과

kms9937 3년 전 0

다익스트라를 돌려서 최단경로에 포함되는 점들을 지우는 과정을 반복해

최단경로와 다른 값의 경로가 나오는 경우 거의 최단경로로 출력을 하게했습니다.

#include<iostream>
using namespace std;
#include<stack>
#include<vector>
#include<queue>
#define INF 987654321
int dist[500];
bool found[500];
int v,e,start,en;
vector<vector<int> >vec[500];
vector<pair<int,int> >path[500];
void ShortestPath()//다익스트라
{   dist[start]=0;
	priority_queue<pair<int,int> >pq;
	pq.push(make_pair(0,start));
	path[start].push_back(make_pair(start,0));
	while(!pq.empty())
    {   int u=pq.top().second;
		int d=-pq.top().first;
		pq.pop();
		if(dist[u]<d)continue;
		for(int i=0;i<vec[u].size();i++)
        {   if(vec[u][i][2]==0)
            {   int v=vec[u][i][0];
                int n=d+vec[u][i][1];
                if(n<dist[v])
                {   dist[v]=n;
                    pq.push(make_pair(-n,v));
                    path[v].clear();
                    path[v].push_back(make_pair(u,i));
                }
                else if(n==dist[v])path[v].push_back(make_pair(u,i));
            }
		}
	}
}
 void checkpath(int k)//최단경로에 포함된 점 삭제
 {  if(k==start)return;
     for(int i=0;i<path[k].size();i++)
     {  int a=path[k][i].first;
        int b=path[k][i].second;
        vec[a][b][2]=1;
        checkpath(a);
     }
 }
int main()
{   cin.tie(0);
    cout.tie(0);
    while(true)
    {   cin>>v>>e;
        if(v==0&&e==0)break;
        cin>>start>>en;
        for(int i=0;i<v;i++)
        {   dist[i]=INF;
            path[i].clear();
        }
        for(int i=0;i<e;i++)
        {   int a,b,c;
            cin>>a>>b>>c;
            vector<int>tmp;
            tmp.push_back(b);
            tmp.push_back(c);
            tmp.push_back(0);
            vec[a].push_back(tmp);
        }
        for(int i=0;i<v;i++)
        {   dist[i]=INF;
            path[i].clear();
        }
        ShortestPath();
        int mindist=dist[en];
        if(mindist>=INF)//최단경로가 없는 경우
        {   cout<<-1<<'\n';
            for(int i=0;i<v;i++)vec[i].clear();
            continue;
        }
        checkpath(en);
        while(true)//최단경로와 다른 값의 경로가 나올 때까지 무한 반복
        {   for(int i=0;i<v;i++)
            {   dist[i]=INF;
                path[i].clear();
            }
            ShortestPath();
            if(dist[en]!=mindist)break;//만약 최단경로와 값이 다른 경로라면 그 경로가 거의 최단경로
            else checkpath(en);
        }
        int ans=dist[en];
        if(ans>=INF)cout<<"-1\n";//거의 최단경로가 없는 경우
        else cout<<ans<<'\n';
        for(int i=0;i<v;i++)vec[i].clear();
    }
}

asdsa2134 3년 전 0

이미 방문한 노드는 방문하지 않도록 처리하면 AC 뜨실거예요

void checkpath(int k)//최단경로에 포함된 점 삭제
 {  
    if(k==start)return;
    // if(visited[k]) return;
    // visited[k] = true;
     for(int i=0;i<path[k].size();i++)
     {  int a=path[k][i].first;
        int b=path[k][i].second;
        vec[a][b][2]=1;
        checkpath(a);
     }
 }

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

문제

문제

출처

ICPC

시간초과

kms9937 3년 전 0

asdsa2134 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말