글 읽기 - 경우를 나누어서 생각해 보았는데 틀리네요ㅠㅠ

jakehsj 7년 전 0

시작-->v1--->v2--->도착

시작--->v2--->v1--->도착

이 두가지 경우를 나누어 생각해 보았는데 예제는 잘 나오는데 틀렸다고 하네요ㅠㅠ 어딜 잘못 생각하거나 실수한걸까요?

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
#define INF 2000000000
#define max_v 202020
using namespace std;

typedef pair<int,int> node;

vector<pair<int,int> >adj[max_v];

priority_queue<node,vector<node>,greater<node> >q;

int n,e;

int d(int x,int y)
{
    int sum=0;
    vector<int> dist1(n+1,INF);
    q.push(node(0,1));
    while(!q.empty())
    {
        int cost=q.top().first;
        int here=q.top().second;
        q.pop();
        if(dist1[here]<cost) continue;
        for(int i=0;i<adj[here].size();i++)
        {
            int ncost=adj[here][i].second+cost;
            int where=adj[here][i].first;
            if(dist1[where]>ncost)
            {
                dist1[where]=ncost;
                q.push(node(ncost,where));
            }
        }
    }
    sum=sum+dist1[x];

    vector<int> dist2(n+1,INF);
    q.push(node(0,x));
    while(!q.empty())
    {
        int cost=q.top().first;
        int here=q.top().second;
        q.pop();
        if(dist2[here]<cost) continue;
        for(int i=0;i<adj[here].size();i++)
        {
            int ncost=adj[here][i].second+cost;
            int where=adj[here][i].first;
            if(dist2[where]>ncost)
            {
                dist2[where]=ncost;
                q.push(node(ncost,where));
            }
        }
    }
    sum=sum+dist2[y];

    vector<int> dist3(n+1,INF);
    q.push(node(0,y));
    while(!q.empty())
    {
        int cost=q.top().first;
        int here=q.top().second;
        q.pop();
        if(dist3[here]<cost) continue;
        for(int i=0;i<adj[here].size();i++)
        {
            int ncost=adj[here][i].second+cost;
            int where=adj[here][i].first;
            if(dist3[where]>ncost)
            {
                dist3[where]=ncost;
                q.push(node(ncost,where));
            }
        }
    }
    sum=sum+dist3[n];
    return sum;
}

int path(int x,int y)
{
    if(d(x,y)>d(y,x))
        if(d(y,x)<INF)
            return d(y,x);
    if(d(x,y)<INF)
        return d(x,y);
    else
        return -1;
}
int main()
{
    scanf("%d%d",&n,&e);
    for(int i=0;i<e;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        adj[a].push_back(make_pair(b,c));
    }
    int rx,ry;
    scanf("%d%d",&rx,&ry);
    printf("%d",path(rx,ry));
    return 0;
}