TOPIC

PROBLEM 1391 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Wyllian Brito replied 6 years ago

    @cr.rusucosmin

    Try this input:

    4 5
    0 2
    0 1 1
    0 3 5
    1 2 2
    1 3 1
    3 2 1
    4 5
    0 2
    0 1 5
    0 3 1
    1 2 1
    3 1 1
    3 2 2
    0 0
  • cr.rusucosmin replied 6 years ago

    #include <fstream>
    #include <iostream>
    #include <vector>
    #include <bitset>
    #include <string.h>
    #include <algorithm>
    #include <iomanip>
    #include <math.h>
    #include <time.h>
    #include <stdlib.h>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <deque>
    
    using namespace std;
    
    const char infile[] = "input.in";
    const char outfile[] = "output.out";
    
    ifstream fin(infile);
    ofstream fout(outfile);
    
    const int MAXN = 505;
    const int oo = 0x3f3f3f3f;
    
    struct trio {
        int nxt, edge, cost;
        trio(int _nxt, int _cost, int _edge) {
            nxt = _nxt;
            cost = _cost;
            edge = _edge;
        }
    };
    
    typedef vector< trio > Graph[MAXN];
    typedef vector< trio > :: iterator It;
    
    const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
    const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
    const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
    const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }
    
    Graph G;
    bitset <MAXN> Used[MAXN];
    int dp[MAXN], N, M, S, D;
    int Father[MAXN];
    
    inline bool Dijkstra() {
        priority_queue <pair<int, int> , vector<pair<int, int> > , greater <pair<int, int> > > Q;
        memset(dp, oo, sizeof(dp));
        dp[S] = 0;
        Q.push(make_pair(0, S));
        while(!Q.empty()) {
            int Node = Q.top().second;
            int cost = Q.top().first;
            Q.pop();
            if(dp[Node] < cost)
                continue;
            if(Node == D)
                continue;
            for(It it = G[Node].begin(), fin = G[Node].end(); it != fin ; ++ it)
                if(!Used[Node][it->nxt] && dp[it->nxt] > cost + it->cost) {
                    dp[it->nxt] = cost + it->cost;
                    Father[it->nxt] = Node;
                    Q.push(make_pair(dp[it->nxt], it->nxt));
                }
        }
        return dp[D] != oo;
    }
    
    int main() {
        /*#ifndef ONLINE_JUDGE
        freopen(infile, "r", stdin);
        freopen(outfile, "w", stdout);
        #endif // ONLINE_JUDGE
        */while(cin >> N >> M) {
            if(!N && !M)
                return 0;
            cin >> S >> D;
            for(int i = 1 ; i <= M ; ++ i) {
                int x, y, z;
                cin >> x >> y >> z;
                G[x].push_back(trio(y, z, i));
            }
            int Ans = oo;
            while(Dijkstra()) {
                if(Ans == oo)
                    Ans = dp[D];
                else if(dp[D] != Ans) {
                    Ans = dp[D];
                    break;
                }
                for(int i = D ; i != S ; i = Father[i])
                    Used[Father[i]][i] = true;
            }
            if(dp[D] == oo || Ans == oo)
                cout << "-1\n";
            else cout << Ans << '\n';
            for(int i = 0 ; i < N ; ++ i) {
                vector < trio > ().swap(G[i]);
                Used[i].reset();
            }
        }
        fin.close();
        fout.close();
        return 0;
    }

    I don't get it... Why do i get WA(10 %) ... Can somebody tell me a "special" case? Thanks in advice!