제출 #202630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202630		SamAnd	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1096 ms	8636 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
const int N = 202, M = 50004;
const long long INF = 1000000009000000009;
struct ban0
{
    int x, y, c, d;
};

int n, m;
ban0 b[M];

struct ban
{
    int x;
    long long d;
    int z;
    int zn;
    ban(){}
    ban(int x, long long d, int z, int zn)
    {
        this->x = x;
        this->d = d;
        this->z = z;
        this->zn = zn;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

vector<ban> a[N];

bool c[N][2][2];

long long djk()
{
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                c[i][j][k] = false;
    priority_queue<ban> q;
    q.push(ban(1, 0, 0, 0));
    long long ans = INF;
    while (1)
    {
        ban t;
        do
        {
            if (q.empty())
            {
                return ans;
            }
            t = q.top();
            q.pop();
        } while (c[t.x][t.z][t.zn]);
        c[t.x][t.z][t.zn] = true;
        if (t.x == 1 && t.zn == 1)
            ans = min(ans, t.d);
        for (int i = 0; i < a[t.x].size(); ++i)
        {
            ban h = a[t.x][i];
            if (t.z && h.z)
                continue;
            h.d += t.d;
            h.z = (t.z | h.z);
            h.zn = (t.zn | h.zn);
            q.push(h);
        }
    }
}

void solv1()
{
    long long ans = INF;
    for (int j = 0; j <= m; ++j)
    {
        for (int i = 1; i <= n; ++i)
            a[i].clear();
        for (int i = 1; i <= m; ++i)
        {
            if (i == j)
            {
                if (b[i].x == n || b[i].y == n)
                {
                    a[b[i].y].push_back(ban(b[i].x, b[i].c, 0, 1));
                }
                else
                {
                    a[b[i].y].push_back(ban(b[i].x, b[i].c, 0, 0));
                }
                continue;
            }
            if (b[i].x == n || b[i].y == n)
            {
                a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 1));
            }
            else
            {
                a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 0));
            }
        }
        if (j == 0)
            ans = min(ans, djk());
        else
            ans = min(ans, djk() + b[j].d);
    }
    if (ans == INF)
        printf("-1\n");
    else
        printf("%lld\n", ans);
}

void solv2()
{
    for (int i = 1; i <= m; ++i)
    {
        if (b[i].x == n || b[i].y == n)
        {
            a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 1));
            a[b[i].y].push_back(ban(b[i].x, b[i].c + b[i].d, 1, 1));
        }
        else
        {
            a[b[i].x].push_back(ban(b[i].y, b[i].c, 0, 0));
            a[b[i].y].push_back(ban(b[i].x, b[i].c + b[i].d, 1, 0));
        }
    }
    long long ans = djk();
    if (ans == INF)
        printf("-1\n");
    else
        printf("%lld\n", ans);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d%d", &b[i].x, &b[i].y, &b[i].c, &b[i].d);
    }
    solv1();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'long long int djk()':
ho_t4.cpp:61:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[t.x].size(); ++i)
                         ~~^~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t4.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &b[i].x, &b[i].y, &b[i].c, &b[i].d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63