Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int main(){
- long long n, m, q, INF = LLONG_MAX;
- cin >> n >> m >> q;
- long long d[n][n];
- for(long long i = 0;i < n;i++)
- for(long long j = 0;j < n;j++){
- d[i][j] = INF;
- if(i == j)
- d[i][j] = 0;
- }
- for(long long i = 0, a, b, w;i < m;i++){
- cin >> a >> b >> w; a--; b--;
- d[a][b] = min(d[a][b], w);
- }
- for(long long k = 0; k < n; ++k) {
- for(long long i = 0; i < n; ++i) {
- for(long long j = 0; j < n; ++j){
- if(d[i][k] < INF && d[k][j] < INF)
- d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
- }
- }
- }
- for (long long i = 0; i < n; ++i) {
- for (long long j = 0; j < n; ++j) {
- for (long long t = 0; t < n; ++t) {
- if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF){
- cout << "NIE";
- return 0;
- }
- }
- }
- }
- for(long long i = 0, a, b;i < q;i++){
- cin >> a >> b; a--; b--;
- if(d[a][b] == INF) cout << "NIE\n";
- else cout << d[a][b] << '\n';
- }
- cout << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement