Submission #1291512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291512		goodpjw2008	Ceste (COCI17_ceste)	C++20	160 / 160	494 ms	25212 KiB

ceste

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct p{
    int x,y,z;
    bool operator>(const p& a) const {
        if(x!=a.x) return x>a.x;
        return y>a.y;
    }
};
vector<p>v[2002];
priority_queue<p,vector<p>,greater<p>>pq;
int ans[2002],bst[2002];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,a,b,t,c;
    cin>>n>>m;
    for(int i = 0; i < m; i++){
        cin>>a>>b>>t>>c;
        v[a].push_back({b,t,c});
        v[b].push_back({a,t,c});
    }
    pq.push({0,0,1});
    for(int i = 2; i <= n; i++)ans[i]=1e15;
    fill(bst,bst+n+1,1e9);
    while(!pq.empty()){
        p cur=pq.top();pq.pop();
        int x=cur.x,y=cur.y,z=cur.z;
        if(y>bst[z])continue;
        bst[z]=y;
        if(y>0&&x>0){
            ans[z]=min(ans[z],x*y);
        }
        for(auto &e:v[z]){
            pq.push({x+e.z,y+e.y,e.x});
        }
    }
    for(int i = 2; i <= n; i++){
        if(ans[i]>=1e15)cout<<-1<<'\n';
        else cout<<ans[i]<<'\n';
    }
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16