Submission #44243

#	Time	Username	Problem	Language	Result	Execution time	Memory
44243		Nnandi	Sightseeing (NOI14_sightseeing)	C++14	15 / 25	3535 ms	131244 KiB

sightseeing

#include <bits/stdc++.h>
#define PB push_back
using namespace std;

struct El {
    int to, w;
    El(int cel, int suly) {
        w=suly;
        to=cel;
    }
    El() { }
    const bool operator< (El masik) const {
        return w<masik.w;
    }
};

const int maxn=500005;

vector<El> graf[maxn];
int d[maxn];
bool volte[maxn];


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin>>n>>m>>q;
    for(int i=0;i<m;i++) {
        int u, v, w;
        cin>>u>>v>>w;
        u--; v--;
        graf[u].PB(El(v,w));
        graf[v].PB(El(u,w));
    }
    El kezdo(0,INT_MAX);
    priority_queue<El> kovi;
    kovi.push(kezdo);
    while(!kovi.empty()) {
        El akt=kovi.top();
        kovi.pop();
        if(!volte[akt.to]) {
            volte[akt.to]=true;
            d[akt.to]=akt.w;
            for(El s:graf[akt.to]) {
                s.w=min(s.w,akt.w);
                if(!volte[s.to] && (d[s.to]==0 || d[s.to]>s.w)) {
                    kovi.push(s);
                }
            }
        }
    }
    vector<int> sol;
    for(int i=0;i<q;i++) {
        int z;
        cin>>z;
        z--;
        sol.push_back(d[z]);
    }
    for(int d:sol) {
        cout<<d<<endl;
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 0 / 10