acmicpc.net 1753(다익스트라), 1916(다익스트라)

https://www.acmicpc.net/problem/1753

한 10번넘게 시도해봤는데 다 시간초과가 뜬다. c++로 코드를 바꾸고 일부 설정을 바꾸니

통과하는걸로보아 그냥 파이썬이 느린 것 같다. 코드를 공부하면서 느낀건데 위상 정렬하고 알고리즘이 

비슷한거같다.

추가.

---

c++로 코드를 짤 경우 cin>>이 느리덴다. scanf가 빠르고. 또 cout<<endl;이 너무 느리니 cout<<'\n'

을 쓰자. 이 사소한 차이때문에 문제를 틀릴 수 있다.

아래 c++코드의 메인 함수의 첫줄 ios::sync_with_stdio(false); 는 cin을 scanf같은것들로 

동기화시켜주는거라고 한다. (printf도 마찬가지.)

사진 출처 : https://algospot.com/forum/read/2496/

---

파이썬 코드(시간초과)

import Queue
def dijkstra(src):
    dist = [999999 for i in xrange(v+1)]
    dist[src] = 0 #시작점은 0
    q = Queue.Queue()
    q.put([src,0]) 
    while not q.empty():
        here,cost = q.get()
        if dist[here] < cost:
            continue
        for i in xrange(len(adj[here])):
            there = adj[here][i][0]
            nextdist = cost + adj[here][i][1]
            if dist[there] > nextdist:
                dist[there] = nextdist
                q.put([there,nextdist])
 
    return dist[1:]
 
v,e = map(int,raw_input().split())
k = input()
adj = [[] for i in xrange(v+1)]
for i in xrange(e):
    s,e,w = map(int,raw_input().split())
    adj[s].append([e,w]) #시작점 s에서 e로 갈수 있고 w만큼의 가중치가 걸린다.
d = dijkstra(k)
for i in d:
    print i if i!=999999 else 'INF'

c++수정(성공)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
 
const long long INF = 999999999;
int V,E,K,u,v,w;
vector<pair<int, int > > adj[20001];
long long dist[20001], visited[20001] = {0,};
    
void dijkstra(int src)
{
    for(int i=0;i<20001;i++)
        dist[i] = INF;
    dist[src] = 0;
    queue<pair<int, int > > q;
    q.push(make_pair(src,0));
    while(!q.empty())
    {
        int here = q.front().first;
        int cost = q.front().second;
        q.pop();
        if(dist[here] < cost)
            continue;
        for(int i=0;i<adj[here].size();i++)
        {
            int there = adj[here][i].first;
            int nextdist = cost + adj[here][i].second;
            if(dist[there] > nextdist)
            {
                dist[there] = nextdist;
                q.push(make_pair(there,nextdist));
            }
        }
    }
}
    
int main()
{
    ios::sync_with_stdio(false); 
    cin>>V>>E>>K;
    for(int i=0;i<E;i++)
    {
        cin>>u>>v>>w;
        adj[u].push_back(make_pair(v,w));
    }
    dijkstra(K);
    
    for(int i=1;i<V+1;i++)
    {
        if(dist[i]==INF)
            cout<<"INF"<<'\n';
        else
            cout<<dist[i]<<'\n';
    }
    return 0;
}

https://www.acmicpc.net/problem/1916

동일한 문제이다. 입력부분만 살짝 바꾸면 된다.

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


const long long INF = 999999999;
int n,m,S,K,u,v,w;
vector<pair<int, int > > adj[20001];
long long dist[20001], visited[20001] = {0,};
   
void dijkstra(int src)
{
    for(int i=0;i<20001;i++)
        dist[i] = INF;
    dist[src] = 0;
    queue<pair<int, int > > q;
    q.push(make_pair(src,0));
    while(!q.empty())
    {
        int here = q.front().first;
        int cost = q.front().second;
        q.pop();
        if(dist[here] < cost)
            continue;
        for(int i=0;i<adj[here].size();i++)
        {
            int there = adj[here][i].first;
            int nextdist = cost + adj[here][i].second;
            if(dist[there] > nextdist)
            {
                dist[there] = nextdist;
                q.push(make_pair(there,nextdist));
            }
        }
    }
}
   
int main()
{
	ios::sync_with_stdio(false); 
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        adj[u].push_back(make_pair(v,w));
    }
	cin>>S>>K;
    dijkstra(S);
    cout<<dist[K]<<'\n';
    
    return 0;
}