acmicpc.net 1238(다익스트라), 4485(다익스트라), 1504(다익스트라)

파이썬으로짜면 시간초과가 나는걸 알기에 c++로 짰다. 파이썬 카테고리인데....

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

다익스트라 문제. 숫자가 적어서 (가는거 + 오는거) 계산하면 된다.

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


const long long INF = 999999999;
int n,m,x,u,v,w;
vector<pair<int, int > > adj[1001];
long long dist[1001];
   
void dijkstra(int src)
{
    for(int i=0;i<1001;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>>x;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        adj[u].push_back(make_pair(v,w));
    }
	int max = -1;
	for(int i=1;i<n+1;i++)
	{
		//cout<<"i = ";
		dijkstra(i);
		int a = dist[x];//cout<<dist[x]<<' ';
		dijkstra(x);
		int b = dist[i];//cout<<dist[i]<<'\n';
		if(max < a+b)
			max = a+b;
	}
	cout<<max<<'\n';
    
    return 0;
}

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

c++코드다. 2차원 배열을 다익스트라로 만들어줘야 한다. 

좀 짜증났던건 2차원배열을 1차원으로 바꾸기위한 식이었다. 

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

const long long INF = 999999999;
int n,m,x,u,v,w;

void dijkstra(int src, vector<pair<int, int > > adj[],int map[][126], long long dist[])
{
    for(int i=0;i<126*126;i++)
        dist[i] = INF;
    dist[src] = map[0][0];
    queue<pair<int, int > > q;
    q.push(make_pair(src,map[0][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); 
	int count = 1;
	while(1)
	{
		vector<pair<int, int > > adj[126*126];
		long long dist[126*126];
		int map[126][126];

		cin>>n;
		if(n==0)
			break;
		for(int i=0;i<n;i++) //map을 입력받음.
			for(int j=0;j<n;j++)
				cin>>map[i][j];

		int x[] = {-1,0,0,1}; //좌,우,위,아래 계산용
		int y[] = {0,-1,1,0};
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{
				for(int k=0;k<4;k++) //좌,우,위,아래를 계산해서
				{
					int ty = i + y[k];
					int tx = j + x[k];
					if(ty<0 || tx<0 || ty>n-1 || tx>n-1) //범위를 벗어나면 continue;
						continue;
					adj[(i*n+j)+1].push_back(make_pair(n*ty + tx+1, map[ty][tx])); //2차원 배열이지만 1차원으로 처리하는게 더 편해서 1차원으로 처리함.
					//cout<<"here = "<<(i*n+j)+1<<" "<<n*ty + tx+1<<" map["<<ty<<"]["<<tx<<"]"<<endl;
				}
				//cout<<'\n';
			}


		dijkstra(1,adj,map,dist); //다익스트라
		/*for(int i=0;i<n;i++) //계산 잘 됬는지 확인용
		{
			for(int j=0;j<n;j++)
				cout<<dist[i*n+j+1]<<" ";
			cout<<endl;
		}
		cout<<'\n';*/

		cout<<"Problem "<<count<<": "<<dist[n*n]<<'\n';//cout<<dist[x]<<' ';
		count++;
	}
    
    return 0;
}

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

쉬운 다익스트라 문제.

1~n까지 가는데 a,b를 반드시 거쳐야되면 최단경로는 1 a b n 또는 a b a n. 

이 경로들 사이사이중 하나라도 끊기는 경로가 있으면 못 가는 것으로 가정한다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
 
const long long INF = 999999999;
int n,e,u,v,w,a,b;
vector<pair<int, int > > adj[801];
long long dist[801];
    
void dijkstra(int src)
{
    for(int i=0;i<801;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>>e;
    for(int i=0;i<e;i++)
    {
        cin>>u>>v>>w;
        adj[u].push_back(make_pair(v,w));
		adj[v].push_back(make_pair(u,w));
    }
	cin>>a>>b;

	int min = INF;
	for(int i=0;i<2;i++)
	{
		int ta=INF,tb=INF,tn=INF,tmax;
		if(i==1)
		{
			int t = b;
				b = a;
				a = t;
		}
		dijkstra(1);
		ta = dist[a];
		
		dijkstra(a);
		tb = dist[b];

		dijkstra(b);
		tn = dist[n];

		if(ta==INF || ta==INF || tn==INF)
			continue;
		tmax = ta+tb+tn;
		if(min > tmax)
			min = tmax;
	}
	if(min!=INF)
		cout<<min<<endl;
	else
		cout<<-1<<endl;
    return 0;
}