Submission #630443

#	Time	Username	Problem	Language	Result	Execution time	Memory
630443		colazcy	Ceste (COCI17_ceste)	C++17	0 / 160	1 ms	340 KiB

ceste

#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
using type = double;
constexpr int maxn = 2e3 + 100;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

struct Vector{
    int x,y;
    Vector operator + (const Vector t)const{return Vector{x + t.x,y + t.y};}
};

int n,m;
type dis[maxn];
Vector vec[maxn];
std::vector<std::pair<int,Vector>> G[maxn];
struct Node{
    int u;
    type h;
    bool operator < (const Node t)const{
        return h > t.h;
    }
};
ll ans[maxn];
void dij(const type t){ // t * x + (1 - t) * y
    static bool vis[maxn];
    static std::priority_queue<Node> q;
    std::fill_n(dis + 1,n,1e9);
    std::fill_n(vec + 1,n,Vector{0x7fffffff,0x7fffffff});
    std::fill_n(vis + 1,n,false);
    vec[1] = Vector{0,0}; dis[1] = 0; q.push(Node{1,0});
    while(!q.empty()){
        let u = q.top().u; q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(let &pir : G[u]){
            let v = pir.first;
            let w = pir.second;
            let m = t * w.x + (1 - t) * w.y;
            if(dis[u] + m < dis[v]){
                dis[v] = dis[u] + m;
                vec[v] = vec[u] + w;
                q.push(Node{v,dis[v]});
            }
        }
    }
    rep(i,2,n)ans[i] = std::min(ans[i],1ll * vec[i].x * vec[i].y);
}
int main(){
#ifndef ONLINE_JUDGE
    std::freopen("fufu.in","r",stdin);
#endif
    std::scanf("%d %d",&n,&m);
    std::fill_n(ans + 1,n,inf);
    repn(m){
        int u,v,t,c; std::scanf("%d %d %d %d",&u,&v,&t,&c);
        G[u].emplace_back(v,Vector{t,c});
        G[v].emplace_back(u,Vector{t,c});     
    }
    type x = 0;
    while(x <= 1.0){
        dij(x);
        type nxt = 1e9;
        rep(u,1,n)
            for(let &pir : G[u]){
                let v = pir.first;
                let w = pir.second;
                let p = (-vec[u].y + vec[v].y - w.y);
                let q = (vec[u].x - vec[u].y + w.x - w.y - vec[v].x + vec[v].y);
                let s = type(p) / q;
                if(s > x)nxt = std::min(nxt,s);
            }
        x = nxt;
    }
    rep(i,2,n)std::printf("%lld\n",ans[i] >= inf ? -1 : ans[i]);
    return 0;
}

Compilation message (stderr)

ceste.cpp: In function 'int main()':
ceste.cpp:59:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     std::freopen("fufu.in","r",stdin);
      |     ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ceste.cpp:61:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     std::scanf("%d %d",&n,&m);
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~
ceste.cpp:64:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         int u,v,t,c; std::scanf("%d %d %d %d",&u,&v,&t,&c);
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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