Submission #28696

#	Time	Username	Problem	Language	Result	Execution time	Memory
28696		ㅁㄴㅇㄹ호 (#68)	Alternative Mart (FXCUP2_mart)	C++14	1 / 1	823 ms	18800 KiB

mart

#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <tuple>
#include <queue>

using namespace std;

struct edg
{
    int x, w;
};

struct str
{
    int x, w, o;
    bool operator <(const str &a) const
    {
        return w > a.w;
    }
};

int pos[50000];
vector<edg> arr[50001];

priority_queue<str> pq;
edg dis[50001][11];

int clo[10];
bool chk[50001];

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    bool u;
    int n, m, k, q, x, y, o, w, nw, s, c, i, j;
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for(i = 0; i<k; i++)
        scanf("%d", &pos[i]);
    for(i = 0; i<m; i++)
    {
        scanf("%d%d%d", &x, &y, &w);
        arr[x].push_back({ y, w });
        arr[y].push_back({ x, w });
    }

    for(i = 1; i<=n; i++)
        for(j = 0; j<11; j++)
            dis[i][j] = { -1, -1 };

    for(i = 0; i<k; i++)
    {
        dis[pos[i]][0] = { pos[i], 0 };
        pq.push({ pos[i], 0, pos[i] });
    }

    while(!pq.empty())
    {
        x = pq.top().x;
        w = pq.top().w;
        o = pq.top().o;
        pq.pop();

        u = 1;
        for(i = 0; i<11; i++)
        {
            if(dis[x][i].x == o && w > dis[x][i].w)
            {
                u = 0;
                break;
            }
        }

        if(!u)
            continue;

        for(edg &e: arr[x])
        {
            y = e.x;
            nw = w + e.w;

            if(dis[y][10].w != -1 && (nw > dis[y][10].w || nw == dis[y][10].w && o >= dis[y][10].x))
                continue;

            u = 1;
            for(i = 0; i<11; i++)
            {
                if(dis[y][i].x == o)
                {
                    if(nw < dis[y][i].w)
                    {
                        for(j = i; j>=0; j--)
                        {
                            if(j == 0 || dis[y][j-1].w != -1 && (nw > dis[y][j-1].w || nw == dis[y][j-1].w && o >= dis[y][j-1].x))
                            {
                                dis[y][j] = { o, nw };
                                break;
                            }
                            dis[y][j] = dis[y][j-1];
                        }

                        pq.push({ y, nw, o });
                    }
                    u = 0;
                    break;
                }
            }

            if(u)
            {
                for(j = 10; j>=0; j--)
                {
                    if(j == 0 || dis[y][j-1].w != -1 && (nw > dis[y][j-1].w || nw == dis[y][j-1].w && o >= dis[y][j-1].x))
                    {
                        dis[y][j] = { o, nw };
                        break;
                    }
                    dis[y][j] = dis[y][j-1];
                }

                pq.push({ y, nw, o });
            }
        }
    }

    for(i = 0; i<q; i++)
    {
        scanf("%d%d", &s, &c);
        for(j = 0; j<c; j++)
            scanf("%d", &clo[j]);

        for(j = 0; j<c; j++)
            chk[clo[j]] = 1;

        for(j = 0; j<11; j++)
        {
            if(!chk[dis[s][j].x])
            {
                printf("%d %d\n", dis[s][j].x, dis[s][j].w);
                break;
            }
        }

        for(j = 0; j<c; j++)
            chk[clo[j]] = 0;
    }
    return 0;
}

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:88:79: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             if(dis[y][10].w != -1 && (nw > dis[y][10].w || nw == dis[y][10].w && o >= dis[y][10].x))
                                                                               ^
mart.cpp:100:108: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                             if(j == 0 || dis[y][j-1].w != -1 && (nw > dis[y][j-1].w || nw == dis[y][j-1].w && o >= dis[y][j-1].x))
                                                                                                            ^
mart.cpp:100:62: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                             if(j == 0 || dis[y][j-1].w != -1 && (nw > dis[y][j-1].w || nw == dis[y][j-1].w && o >= dis[y][j-1].x))
                                                              ^
mart.cpp:119:100: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                     if(j == 0 || dis[y][j-1].w != -1 && (nw > dis[y][j-1].w || nw == dis[y][j-1].w && o >= dis[y][j-1].x))
                                                                                                    ^
mart.cpp:119:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                     if(j == 0 || dis[y][j-1].w != -1 && (nw > dis[y][j-1].w || nw == dis[y][j-1].w && o >= dis[y][j-1].x))
                                                      ^
mart.cpp:43:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &k, &q);
                                      ^
mart.cpp:45:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &pos[i]);
                             ^
mart.cpp:48:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &w);
                                    ^
mart.cpp:134:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &s, &c);
                              ^
mart.cpp:136:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &clo[j]);
                                 ^

• Subtask 1: 1 / 1