| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 629820 |
2022-08-15T08:14:24 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.y};}
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 spfa{
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){
assert(w.first >= 0);
G[u].emplace_back(v,w);
G[v].emplace_back(u,w);
}
void clear(){
rep(i,1,n)G[i].clear();
}
std::queue<int> q;
bool inq[maxn];
ll dis[maxn];
Vector vec[maxn];
bool spfa(const int tag){
std::fill_n(inq + 1,n,false);
std::fill_n(dis + 1,n,0x3f3f3f3f3f3f3f3f);
while(!q.empty())q.pop();
q.push(1);
dis[1] = 0; inq[1] = 1;
while(!q.empty()){
let u = q.front(); q.pop(); inq[u] = 0;
if(dis[u] < 0)return false;
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;
if(!inq[v])q.push(v),inq[v] = 1;
}
}
}
return true;
}
}
ll ans;
void solve(const int tag,const Point a,const Point b){
spfa::clear();
rep(i,1,m){
let x = edges[i].w.x,y = edges[i].w.y;
ll t = (b.x - a.x) * y + (a.y - b.y) * x;
spfa::addedge(edges[i].u,edges[i].v,{t,edges[i].w});
}
if(!spfa::spfa(tag))return;
let p = spfa::vec[tag];
ans = std::min(ans,p.x * p.y);
if((b - a) * (p - a) >= 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;
spfa::clear();
rep(i,1,m)spfa::addedge(edges[i].u,edges[i].v,{edges[i].w.x,edges[i].w});
spfa::spfa(i);
if(spfa::dis[i] == 0x3f3f3f3f3f3f3f3f){
std::puts("-1");
continue;
}
const Point a = spfa::vec[i];
ans = std::min(ans,spfa::vec[i].x * spfa::vec[i].y);
spfa::clear();
rep(i,1,m)spfa::addedge(edges[i].u,edges[i].v,{edges[i].w.y,edges[i].w});
spfa::spfa(i);
const Point b = spfa::vec[i];
ans = std::min(ans,spfa::vec[i].x * spfa::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 |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 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 |
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 |
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 |
- |
