글 읽기 - 문제가 이해가 가지 않아서 질문드립니다.

yulran 6년 전 0

아래와 같이 다이젝스트라로 최단거리를 구하는데

처음 풀이는 a,b형 중에 가장 거리가 짧은 것을 리턴하였는데 풀이가 틀리다고 나와서

두번째는 a,b형 중에 k개 모두 진서집에 도달 가능 여부를 확인하여 둘다 가능하면 최솟값인 것을

하나만 도달하면 도달하는 것을

둘다 k개가 안되면 -1로 바꿧는데 역시 틀리다고 나옵니다.

문제가 제대로 이해가 가지 않는데 알려주시면 감사하겠습니다.

단순 둘다 모두 도달 안되는경우(즉 a,b 둘다 0개) -1

아닌 경우 가장 작은값을 출력하면 됩니다.......

#include <iostream> 
#include <iterator>
#include <algorithm> 
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define MOD 1000000007
#define INF 2147483647
#define LNF 9223372036854775807
#define pb push_back
#define mp make_pair
#define f first
#define s second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

int n,m,home,k,homeType[5001];
struct Node{
   	int dest, weight;
	Node(int b,int c):dest(b),weight(c){}
	Node():dest(0),weight(0){}
	bool operator<(const Node rhs)const{return weight>rhs.weight;}
};
vector<Node> edges[5001];
pii dijkstraAlgo(int start){
	priority_queue<Node> que;
	vector<int> dist(n+1, 1000000);
    dist[start] = 0;
    que.push(Node(start,0));
    while(!que.empty()){
		Node v = que.top();
    	que.pop();
    	if(v.weight>dist[v.dest]) continue;
        for(int i=0;i<edges[v.dest].size();i++){
        	Node u = edges[v.dest][i];
        	if(dist[u.dest]>v.weight+u.weight){
        		dist[u.dest] = v.weight + u.weight;
        		que.push(Node(u.dest,dist[u.dest]));
        	}
        }
	}
	int aCnt=0,bCnt=0,aMin=1000000,bMin=1000000;
	for(int i=1;i<=n;i++){
		if(dist[i]!=1000000){
			if(homeType[i]==1){
				aCnt++;
				aMin=min(aMin,dist[i]);
			}
			else if(homeType[i]==2){
				bCnt++;
				bMin=min(bMin,dist[i]);
			}
		}
	}
	if(aCnt==k && bCnt==k) return aMin<=bMin?mp(1,aMin):mp(2,bMin);
	else if(aCnt==k) return mp(1,aMin);
	else if(bCnt==k) return mp(2,bMin);
	else return mp(0,0);
}
int main(){
	freopen("sample.txt","r",stdin);
	scanf("%d%d%d%d",&n,&m,&home,&k);
	for(int i=0,a;i<k;i++){
		scanf("%d",&a);
		homeType[a]=1;
	}
	for(int i=0,a;i<k;i++){
		scanf("%d",&a);
		homeType[a]=2;
	}
	for(int i=0,x,y,z;i<m;i++){
		scanf("%d%d%d",&x,&y,&z);
		edges[x].pb(Node(y,z));
		edges[y].pb(Node(x,z));
	}
	pii ret = dijkstraAlgo(home);
	if(ret.f==0) printf("-1\n");
	else printf("%c\n%d\n",ret.f==1?'A':'B',ret.s);
	return 0;
}

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

문제

문제

출처

ICPC

문제가 이해가 가지 않아서 질문드립니다.

yulran 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말