It's been a long time and it seems like they have completely forgotten that they need to rollback and recalculate ratings after plag check.Its been a month.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
It's been a long time and it seems like they have completely forgotten that they need to rollback and recalculate ratings after plag check.Its been a month.
// this code doesnt work unless you comment the lines 71-73 part...
// proof:
/*
input
5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 5 1000
1
then input
5 5
1 5 1000
1 2 1
2 3 1
3 4 1
4 5 1
1
if you un-comment the lines, both output differently.
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) (v).begin(), (v).end()
#define endl '\n'
#define MOD 1000000007
ll mod(ll a) {
return (a%MOD + MOD)%MOD;
}
ll binpow(ll x, ll n) {
if (n == 0) {
return 1;
}
if (x == 0) {
return 0;
}
if (n%2 == 0) {
ll temp = binpow(x,n/2);
return mod(temp*temp);
}
return mod(mod(x)*binpow(x,n-1));
}
void print(bool& ans) { cout << (ans ? "YES" : "NO") << endl; }
// now we have weights(positive). Had weights were negative, we couldnot have used it.
#define f first
#define s second
vector<vector<pair<ll,ll>>> adj;
vector<ll> vis, dis;
void sssp(int src) {
dis[src] = 0;
queue<ll> q;
q.push(src);
while (!q.empty()) {
int node = q.front();
q.pop();
// if (vis[node]) { // the code works when you comment this part, because now for every time a node is pushed, it checks for distance.
// continue;
// }
vis[node] = 1;
for (auto &x:adj[node]) {
if (dis[x.f] > dis[node] + x.s) {
dis[x.f] = dis[node] + x.s;
q.push(x.f);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
adj = vector<vector<pair<ll,ll>>> (n+1);
vis = vector<ll> (n+1,0);
dis = vector<ll> (n+1,1e9);
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
int src;
cin >> src;
sssp(src);
for (int i = 1; i <= n; i++) {
cout << i << ": " << dis[i] << endl;
}
return 0;
}
WHAT IS THE TIME COMPLEXITY OF THIS APPROACH? IS THIS BETTER THAN OTHER SSSP ALGORITHMS?
Name |
---|