Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#define pii pair
#define MAXN 10010 using namespace std; const int MOD = (int)1e9+7; vector
grafo[MAXN]; int dist[MAXN], pai[MAXN], rota[MAXN], min_vrota[MAXN], max_vrota[MAXN]; /* rota[i]: nro de caminhos minimos para chegar no vértice i min_vrota[i]: menor nro de vértices dentre as menores rotas até i max_vrota[i]: maior nro de vértices dentre as menores rotas até i */ void dijkstra(int s){ set
q; q.insert({0,s}); dist[s] = 0; rota[s] = 1; min_vrota[s] = 1; max_vrota[s] = 1; while(!q.empty()){ int v = q.begin()->second; q.erase(q.begin()); for(auto [w,u] : grafo[v]){ if(dist[v]+w < dist[u]){ q.erase({dist[u],u}); dist[u] = dist[v]+w; q.insert({dist[u],u}); pai[u] = v; rota[u] = rota[v]; min_vrota[u] = min_vrota[v]+1; max_vrota[u] = max_vrota[v]+1; }else if(dist[v]+w == dist[u]){ rota[u] += rota[v]; rota[u] %= MOD; min_vrota[u] = min(min_volta[u],min_vrota[v]+1); max_vrota[u] = max(max_vrota[u],max_vrota[v]+1); } } } } int main(){ int n, m; scanf("%d %d", &n, &m); for(int i = 0; i < m; i++){ int a, b, c; scanf("%d %d %d", &a, &b, &c); grafo[a].push_back({c,b}); } // }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)