글 읽기 - 도대체 어디서 틀렷을까요

zmfldlwl 8년 전 0

시간초과까지 다 해결햇는데...

어디서 틀렷을까요 ...

#include <iostream>
#include <memory.h>
#include <queue>
#include <stdio.h>
#include <vector>
#include <map>
#include <functional> 

using namespace std;

class Edge
{
public:
    int z;
    int x;
    int y;
    int depth;
    Edge() {}
    Edge(int a, int b, int c, int d)
    {
        z = a;
        x = b;
        y = c;
        depth = d;
    }
    bool operator > (const Edge &v) const
    {
        return z < v.z;
    }
};

int n, m;
int ss, ee;

priority_queue<Edge, vector<Edge>, greater<Edge> > qq;
vector<Edge> v[10005];
int res[10005];

queue<int> qq1;
vector<int> v1[10005];

bool visit[10005];

int main()
{
    cin >> n >> m;

    int a, b, c;

    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back(Edge(c, a, b, 0));
    }

    cin >> ss >> ee;

    int s = v[ss].size();
    Edge temp;

    qq.push(Edge(0, 0, ss, 0));

    int r_max = -2100000000;
    int r_depth = -2100000000;

    while (!qq.empty())
    {
        temp = qq.top();
        qq.pop();

        s = v[temp.y].size();

        for (int i = 0; i < s; i++)
        {
            int g = res[v[temp.y].at(i).y];
            int g1 = (res[temp.y] + v[temp.y].at(i).z);

            if (res[v[temp.y].at(i).y] < (res[temp.y] + v[temp.y].at(i).z))
            {
                res[v[temp.y].at(i).y] = (res[temp.y] + v[temp.y].at(i).z);

                v1[v[temp.y].at(i).y].clear();
                v1[v[temp.y].at(i).y].push_back(v[temp.y].at(i).x);

                qq.push(Edge(v[temp.y].at(i).z, v[temp.y].at(i).x, v[temp.y].at(i).y, temp.depth + 1));
            }
            else if (res[v[temp.y].at(i).y] == (res[temp.y] + v[temp.y].at(i).z))
            {
                v1[v[temp.y].at(i).y].push_back(v[temp.y].at(i).x);
            }
        }

        if (qq.empty())
            break;
    }

    memset(visit, 0, sizeof(visit));
    //도착부터 거꾸로, 가중치
    
    int ll = 0;

    qq1.push(ee);
    visit[ee] = true;

    while (!qq1.empty())
    {
        int temp = qq1.front();
        qq1.pop();

        if (temp == ss)
            continue;

        int l = v1[temp].size();

        for (int i = 0; i < l; i++)
        {
            ll++;

            if (!visit[v1[temp].at(i)])
            {
                visit[v1[temp].at(i)] = true;
                qq1.push(v1[temp].at(i));
            }
        }
    }

    cout << res[ee] << endl;
    cout << ll << endl;

    return 0;
}

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

문제

문제

출처

ICPC

도대체 어디서 틀렷을까요

zmfldlwl 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말