답안 #28696 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28696	2017-07-16T08:48:11 Z	ㅁㄴㅇㄹ호(#1227, gs13105)	Alternative Mart (FXCUP2_mart)	C++14	1 / 1	823 ms	18800 KB

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

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.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6888 KB	Output is correct
2	Correct	0 ms	6888 KB	Output is correct
3	Correct	0 ms	6888 KB	Output is correct
4	Correct	0 ms	6888 KB	Output is correct
5	Correct	0 ms	6888 KB	Output is correct
6	Correct	0 ms	6888 KB	Output is correct
7	Correct	3 ms	7032 KB	Output is correct
8	Correct	3 ms	6888 KB	Output is correct
9	Correct	6 ms	7644 KB	Output is correct
10	Correct	13 ms	7640 KB	Output is correct
11	Correct	29 ms	7344 KB	Output is correct
12	Correct	26 ms	7020 KB	Output is correct
13	Correct	146 ms	13808 KB	Output is correct
14	Correct	159 ms	13788 KB	Output is correct
15	Correct	86 ms	9024 KB	Output is correct
16	Correct	143 ms	8472 KB	Output is correct
17	Correct	376 ms	9992 KB	Output is correct
18	Correct	349 ms	8472 KB	Output is correct
19	Correct	506 ms	11148 KB	Output is correct
20	Correct	356 ms	8472 KB	Output is correct
21	Correct	549 ms	11144 KB	Output is correct
22	Correct	396 ms	8624 KB	Output is correct
23	Correct	516 ms	13448 KB	Output is correct
24	Correct	506 ms	10840 KB	Output is correct
25	Correct	533 ms	13448 KB	Output is correct
26	Correct	523 ms	10840 KB	Output is correct
27	Correct	113 ms	9464 KB	Output is correct
28	Correct	109 ms	9168 KB	Output is correct
29	Correct	543 ms	11472 KB	Output is correct
30	Correct	429 ms	9956 KB	Output is correct
31	Correct	573 ms	13612 KB	Output is correct
32	Correct	463 ms	9844 KB	Output is correct
33	Correct	533 ms	11224 KB	Output is correct
34	Correct	693 ms	13908 KB	Output is correct
35	Correct	626 ms	13608 KB	Output is correct
36	Correct	699 ms	13744 KB	Output is correct
37	Correct	776 ms	18532 KB	Output is correct
38	Correct	696 ms	13840 KB	Output is correct
39	Correct	136 ms	10152 KB	Output is correct
40	Correct	129 ms	10152 KB	Output is correct
41	Correct	669 ms	14180 KB	Output is correct
42	Correct	646 ms	14188 KB	Output is correct
43	Correct	759 ms	14184 KB	Output is correct
44	Correct	759 ms	14188 KB	Output is correct
45	Correct	793 ms	14184 KB	Output is correct
46	Correct	766 ms	14192 KB	Output is correct
47	Correct	756 ms	18788 KB	Output is correct
48	Correct	783 ms	18792 KB	Output is correct
49	Correct	786 ms	18792 KB	Output is correct
50	Correct	823 ms	18800 KB	Output is correct
51	Correct	566 ms	18784 KB	Output is correct
52	Correct	613 ms	18788 KB	Output is correct
53	Correct	229 ms	8472 KB	Output is correct
54	Correct	656 ms	13876 KB	Output is correct
55	Correct	659 ms	13852 KB	Output is correct
56	Correct	813 ms	14180 KB	Output is correct
57	Correct	113 ms	11132 KB	Output is correct

답안 #28696

Compilation message

Subtask #1 1.0 / 1.0

Subtask #1
1.0 / 1.0