제출 #637522

#제출 시각아이디문제언어결과실행 시간메모리
637522HuyRobot (JOI21_ho_t4)C++17
0 / 100
79 ms43344 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<int,int> #define fi first #define se second /*#pragma GCC tarGet ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC tarGet("avx,avx2,fma")*/ using namespace std; using ll = long long; using ull = unsigned long long; using ldb = long double; const int N = 1e5; const int maxN = 2e5 + 1; const int mod = 1e9 + 7; const int block_size = 700; const ll infty = 1e18; struct Tpq { int ver,pre; ll val; }; struct functer { bool operator()(Tpq a,Tpq b) { return a.val > b.val; } }; int n,m; int x[maxN],y[maxN],c[maxN],p[maxN]; vector<int> adj[maxN]; ll dp[1005][1005]; int cnt[maxN]; void Read() { cin >> n >> m; for(int i = 1;i <= m;i++) { cin >> x[i] >> y[i] >> c[i] >> p[i]; adj[x[i]].push_back(i); adj[y[i]].push_back(i); } } void Dijkstra() { for(int i = 1;i <= n;i++) { for(int j = 0;j <= n;j++) { dp[i][j] = infty; } } priority_queue<Tpq,vector<Tpq>,functer> q; dp[1][0] = 0; q.push({1,0,0}); do { Tpq pick = q.top(); q.pop(); int u = pick.ver; int pre = pick.pre; if(dp[u][pre] != pick.val) continue; for(int i : adj[u]) { int v = x[i] + y[i] - u; if(v == pre) continue; cnt[c[i]]++; } for(int i : adj[u]) { int v = x[i] + y[i] - u; //if(v == pre) continue; if(dp[v][u] > dp[u][pre] + (cnt[c[i]] > 1) * p[i]) { dp[v][u] = dp[u][pre] + (cnt[c[i]] > 1) * p[i]; q.push({v,u,dp[v][u]}); } } for(int i : adj[u]) { cnt[c[i]] = 0; } } while(!q.empty()); } void Solve() { Dijkstra(); ll res = infty; for(int i = 0;i <= n;i++) { res = min(res,dp[n][i]); } if(res >= infty) res = -1; cout << res; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //InputFile(); //int sub_type; //cin >> sub_type; //Sieve(); int test; //cin >> test; test = 1; while(test--) //for(int prc = 1; prc <= test; prc++) { Read(); Solve(); //Debug(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...