| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 629802 |
2022-08-15T07:50:16 Z |
colazcy |
Ceste (COCI17_ceste) |
C++17 |
|
1 ms |
340 KB |
#include <cstdio>
#include <cassert>
#include <vector>
#include <utility>
#include <queue>
#define let const auto
#define rep(name,beg,end) for(auto name = beg,name##_end = end;name <= name##_end;name++)
#define per(name,beg,end) for(auto name = beg,name##_end = end;name >= name##_end;name--)
#define repn(lim) for(auto NOW = 1,END = lim;NOW <= END;NOW++)
#define debug(...) std::fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
using i128 = __int128_t;
constexpr int maxn = 2e3 + 100;
struct Vector{
ll x,y;
Vector operator + (const Vector t)const{return Vector{x + t.x,y + t.y};}
Vector operator - (const Vector t)const{return Vector{x - t.x,y - t.x};}
i128 operator * (const Vector t)const{return i128(x) * t.y - i128(y) * t.x;}
};
using Point = Vector;
int n,m;
struct Edge{
int u,v;
Vector w;
}edges[maxn];
namespace dij{
std::vector<std::pair<int,std::pair<ll,Vector>>> G[maxn];
void addedge(const int u,const int v,const std::pair<ll,Vector> w){
G[u].emplace_back(v,w);
G[v].emplace_back(u,w);
}
void clear(){
rep(i,1,n)G[i].clear();
}
struct Node{
int u;
ll h;
bool operator < (const Node t)const{
return h > t.h;
}
};
std::priority_queue<Node> q;
bool vis[maxn];
ll dis[maxn];
Vector vec[maxn];
void dij(const int tag){
std::fill_n(vis + 1,n,false);
std::fill_n(dis + 1,n,0x3f3f3f3f3f3f3f3f);
while(!q.empty())q.pop();
q.push(Node{1,0}); dis[1] = 0;
while(!q.empty()){
let u = q.top().u; q.pop();
if(u == tag)return;
if(vis[u])continue;
vis[u] = 1;
for(let &pir : G[u]){
let v = pir.first;
let w = pir.second.first;
let t = pir.second.second;
if(dis[u] + w < dis[v]){
dis[v] = dis[u] + w;
vec[v] = vec[u] + t;
q.push(Node{v,dis[v]});
}
}
}
}
}
ll ans;
void solve(const int tag,const Point a,const Point b){
dij::clear();
rep(i,1,m)dij::addedge(edges[i].u,edges[i].v,{edges[i].w.x * (b.y - a.y) + edges[i].w.y * (a.x - b.x),edges[i].w});
dij::dij(tag);
let p = dij::vec[tag];
ans = std::min(ans,p.x * p.y);
if(p.x * (b.y - a.y) + p.y * (a.x - b.x) - a.x * b.y + a.y * b.x <= 0)return;
solve(tag,a,p);
solve(tag,p,b);
}
int main(){
#ifndef ONLINE_JUDGE
std::freopen("fufu.in","r",stdin);
// std::freopen("fufu.out","w",stdout);
#endif
std::scanf("%d %d",&n,&m);
rep(i,1,m)
std::scanf("%d %d %lld %lld",&edges[i].u,&edges[i].v,&edges[i].w.x,&edges[i].w.y);
rep(i,2,n){
ans = 0x7fffffffffffffff;
dij::clear();
rep(i,1,m)dij::addedge(edges[i].u,edges[i].v,{edges[i].w.x,edges[i].w});
dij::dij(i);
if(dij::dis[i] == 0x3f3f3f3f3f3f3f3f){
std::puts("-1");
continue;
}
const Point a = dij::vec[i];
ans = std::min(ans,dij::vec[i].x * dij::vec[i].y);
dij::clear();
rep(i,1,m)dij::addedge(edges[i].u,edges[i].v,{edges[i].w.y,edges[i].w});
dij::dij(i);
const Point b = dij::vec[i];
ans = std::min(ans,dij::vec[i].x * dij::vec[i].y);
solve(i,a,b);
std::printf("%lld\n",ans);
}
return 0;
}
Compilation message
ceste.cpp: In function 'int main()':
ceste.cpp:90:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | std::freopen("fufu.in","r",stdin);
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ceste.cpp:93:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | std::scanf("%d %d",&n,&m);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
ceste.cpp:95:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | std::scanf("%d %d %lld %lld",&edges[i].u,&edges[i].v,&edges[i].w.x,&edges[i].w.y);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
