TÓPICO

PROBLEM 1148 - URI Fórum 1.0

URI Online Judge perguntou 8 years ago

URI Online Judge Fórum 1.0

MOD

Este tópico foi resolvido e não pode receber novas respostas.

  • Jairo S. respondido 5 years ago

    Seu código não responde essa entrada:

    5 0
    2
    1 3
    4 5
    0 0

    A resposta deveria ser:

    Nao e possivel entregar a carta
    Nao e possivel entregar a carta

     

  • NIGHTSX respondido 5 years ago

    Estou levando TLE aqui, alguém tem uma dica de como melhorar o desempenho do algoritmo? Tenho a impressão de que existe uma forma melhor de saber se as cidades estão no mesmo país.

    Resolvido...
  • Rafael Gauna Trindade respondido 5 years ago

    Oi amigo. Pensei dessa forma também para a implementação. Porém usei Dijkstra e matriz de adjacências/pesos, com cada cidade contendo a lista de cidades que pode alcançar do modo unidirecional (pra não ter que percorrer a linha da matriz). Também defino 0 na matriz de adjacencias/pesos caso as cidades tenham conexão duplex, e deixo -1 caso não exista uma conexão.

    Tenho também um vetor de pesos para armazenar o resultado de pesos mínimos totais dos djikstras pra cada o usado nos casos de teste (não processo djikstras desnecessariamente).

    Estou conseguindo 10% de WA. Aqui o código:

    https://gist.github.com/648trindade/c64 ... b54f0abfa0

    Testei nas entradas que o pessoal sugeriu aqui no fórum e tá dando certo.

    Creio que não seja problema de memória. No pior caso o programa consome aprox. 1.15 MB pra uma máquina de 32 bits e 2.3 MB pra uma de 64 bits

    Onde posso estar errando?

  • Old man respondido 6 years ago

    Não preciso mais de ajuda neste problema, desde o dia 29-04-2014 estudando e tentando resolvê-lo, porém finalmente eu consegui.

    Obrigado pelas dicas.

  • André Alves respondido 6 years ago

    Esse exercício é resolvido com o algorítimo do menor caminho de grafos, eu utilizei o Dijkstra.

    Com a implementação feita (genérica mesmo, não tem nada de especial para esse exercício) basta aplica-la no grafo montado. O que ficou mal explicado no exercício é a condição para que as agências A e B estejam no mesmo país.

    Mas basicamente é isso:

    Se existe ligação da agência A para agência B e também existe uma ligação da agência B para agência A, então ambas as ligações devem ter valor 0;

    for(i = 0; i < e; i++) {
                scanf("%d %d %d", &x, &y, &h);
                grafo[x-1][y-1] = h;
    
                if(grafo[y-1][x-1] != INF) {
                    grafo[x-1][y-1] = 0;
                    grafo[y-1][x-1] = 0;
                }
            }

    Só isso, tente fazer com matriz de adj e não use 0 para demonstrar que não existe ligação, faça com um #define INFINITO com um valor absurdo.

    EDIT

    Vi agora que você tinha postado um código. Bom, a sua ideia da montagem do grafo está igual o que eu escrevi acima, mas sua implementação do menor caminho deve estar errada. Minha recomendação é que você procure vídeos no youtube ensinando o algorítimo do Dijkstra. Depois de entender como funciona, se tiver dificuldades pra fazer sua implementação, no site geeksforgeeks eles ensinam a implementar também.

  • Unknown respondido 4 years ago

    O meu código está apresentado runtime error. Não consigo entender o porque... ajudem ai, por favor.

    include include include include

    using namespace std;

    bool visitados; int distancia;

    typedef struct node { int vertice; int custo; } Node;

    struct node_cmp { bool operator()(const Node a, const Node b) const { return a->custo < b->custo; } };

    priority_queue<Node, std::vector<Node>, node_cmp> frontier;

    int matrix[501][501]; int size;

    int shortestPath(int origem, int destino) {

    Node *nodoCorrente = new Node;
    
    distancia[origem] = 0;
    
    nodoCorrente->vertice = origem;
    nodoCorrente->custo = 0;
    
    frontier.push(nodoCorrente);
    
    int u, v;
    while (!frontier.empty()) {
        nodoCorrente = frontier.top();
        frontier.pop();
    
        u = nodoCorrente->vertice;
    
        //if (visitados[u])
        //  continue;
    
        if (u == destino){
            return distancia[u];
            free(nodoCorrente);
        }
    
        int i;
        for (i = 1; i <= size; i++){
            if (matrix[u][i] != -1) {
    
                int v = i;
                int w_edge = matrix[u][i];
    
                if (!visitados[v]) {
    
                    if (distancia[u] + w_edge < distancia[v]) {
    
                        Node *vizinho = new Node;
                        vizinho->vertice = v;
                        vizinho->custo = distancia[u] + w_edge;
                        distancia[v] = distancia[u] + w_edge;
    
                        frontier.push(vizinho);
    
                        //free(vizinho);
                    }
    
                }
            }
        }
    
        visitados[u] = true; //adiciona como explorado
    }
    free(nodoCorrente);
    return -1; //heap vazia e não chegou ao destino

    }

    int main() {

    int n = 1, m;
    int x, y, h;
    int numeroConsultas;
    int origem, destino;
    int elapsedTime;
    int i, j;
    
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0)
            break;
    
        size = n;
    
        visitados = new bool[n + 1];
        distancia = new int[n + 1];
        int i;
        for (i = 0; i <= n; i++){
            for (j = 0; j <= n; j++){
                matrix[i][j] = -1;
            }
        }
    
        while (m--) {
            cin >> x >> y >> h;
            matrix[x][y] = h;
        }
    
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (matrix[i][j] != -1 && matrix[j][i] != -1){
                    matrix[i][j] = 0;
                    matrix[j][i] = 0;
                }
            }
        }
    
        cin >> numeroConsultas;
    
        while (numeroConsultas--) {
    
            for (i = 1; i <= n; i++) {
                visitados[i] = false;
                distancia[i] = std::numeric_limits<int>::max(); //infinito
            }
    
            for (i = 1; i <= n; i++) {
                for (j = 1; j <= n; j++) {
                    if (matrix[i][j] != -1 && matrix[j][i] != -1){
                        matrix[i][j] = 0;
                        matrix[j][i] = 0;
                    }
                }
            }
    
            cin >> origem >> destino;
            elapsedTime = shortestPath(origem, destino);
    
            elapsedTime == -1 ? cout << "Nao e possivel entregar a carta" << endl : cout << elapsedTime << endl;
        }
        cout << "\n";
    
    }
    
    return 0;

    }

  • Allyson Dias de Lima respondido 4 years ago

    Qual é o melhor algoritmo para utilizar e por quê?

    Existem algoritmos de uma origem para todos os destinos como o Dijkstra, mas existem outros algoritmos que já calculam para todos os pares de pontos então uma vez calculados todos, basta imprimir. São eles: algoritmo de Floyd-Warshall e Algoritmo de Johnson (mais rápido) e ainda algoritmos que busca a menor distância para apenas um par de cada vez.

    Inicialmente resolvi com Floyd-Warshall mas deu um tempo muito alto. Quero otimizá-lo.

  • Lucas Castro respondido 5 years ago

    Wrong answer 100% ... alguem sabe porquê? Usei Floyd-Warshall...

    #include<stdio.h>
    #define INF 2000000
    #define MIN(a,b) (a)<(b)?(a):(b)
    int d[501][501];
    int main(){
        while(1){
            int n,m,i,j,k,x,y,z;
            scanf("%d %d",&n,&m);
            if(n==0 || 0==m)break;
            for(i=1;i<=n;i++){
                for(j=1;j<=n;j++){
                    d[i][j]=INF;
                    if(i==j)d[i][i]=0;
                }
            }
            for(i=0;i<m;i++){
                scanf("%d %d %d",&x,&y,&z);
                if(d[y][x]!=INF || d[x][y]!=INF){
                    d[x][y]=0;
                    d[y][x]=0;
                }
                else {
                    d[x][y]=z;
                }
            }
            for(k=1;k<=n;k++){
                for(i=1;i<=n;i++){
                    for(j=1;j<=n;j++){
                        d[i][j]=MIN(d[i][j],d[i][k]+d[k][j]);
                    }
                }
            }
            scanf("%d",&m);
            for(i=0;i<m;i++){
                scanf("%d %d",&x,&y);
                if(d[x][y]==INF)printf("Nao e possivel entregar a carta\n");
                else printf("%d\n",d[x][y]);
            }
            printf("\n");
        }
        return 0;
    }
  • Paulo Felipe respondido 5 years ago

    Cara obrigado pela resposta, mas eu encontrei o erro, era na implementação do algoritmo do Dijkstra e na hora de preencher a lista de adjacência.

    Obrigado pela resposta!

  • Jairo S. respondido 5 years ago

      Como a entrada desse problema é pequena (N <= 500) também é possível resolver com Floyd-Warshall que é MUITO mais fácil e rápido de implementar em comparação com Dijkstra.  

  • Paulo Felipe respondido 5 years ago

    Você tem que verificar se o vértice V ainda está na fila.

  • Paulo Felipe respondido 5 years ago

    Pessoal implementei com matriz de adjacência e com lista de adjacência porém ainda continua dando Wrong Answer 100%!

    Alguma alma boa pode me ajudar?

    #include <iostream>
    #include <queue>
    #include <vector>
    #include <functional>
    #include <map>
    #include <limits>
    #define MAX 500
    using namespace std;
    map<int, int>custos;
    int MATRIZ[MAX][MAX];
    int dijktra(int ori, int des, int vert);
    class comp
    {
        bool rever;
    public:
        comp(const bool& revparam=false)
        { rever = revparam; }
        bool operator() (const int& lhs, const int&rhs) const
        {
            if(rever)
                return (custos[lhs]>custos[rhs]);
            else
                return (custos[lhs]<custos[rhs]);
        }
    };
    int main()
    {
        int vert, ar, v1, v2, peso, k, ret;
        while(cin>>vert>>ar && (vert || ar))
        {
            for(int i=0;i<vert;i++)
                for(int j=0;j<vert;j++)
                    MATRIZ[i][j] = -1;
            for(int i=0;i<ar;i++)
            {
                cin>>v1>>v2>>peso;
                if(MATRIZ[v2-1][v1-1]!=-1)//conexão dupla
                {
                    MATRIZ[v2-1][v1-1] = 0;
                    MATRIZ[v1-1][v2-1] = 0;
                }
                else
                    MATRIZ[v1-1][v2-1] = peso;
            }
            cin>>k;
            for(int i=0;i<k;i++)
            {
                cin>>v1>>v2;
                ret = dijktra(v1-1, v2-1, vert);
                if(ret==-1)
                    cout<<"Nao e possivel entregar a carta"<<endl;
                else
                    cout<<ret<<endl;
            }
            cout<<endl;
        }
        return 0;
    }
    int dijktra(int ori, int des, int vert)
    {
        typedef priority_queue<int, vector<int>, comp>mypq;
        mypq fila (comp(true));
        map<int, bool>inlist; map<int, int>precede; vector<int>pilha;
        int v, w, soma = 0;
        for(int i=0;i<vert;i++)
        {
            if(i!=ori)
                custos[i] = numeric_limits<int>::max();
            else
                custos[i] = 0;
            fila.push(i);
        }
        while(!fila.empty())
        {
            v = fila.top(); inlist[v] = true;
            for(int i=0;i<vert;i++)
            {
                if(MATRIZ[v][i]!=-1)
                {
                    w = i;
                    if(inlist[w]==false)
                    {
                        if(custos[w]>(custos[v]+MATRIZ[v][w]))
                        {
                            custos[w] = custos[v]+MATRIZ[v][w];
                            precede[w] = v;
                        }
                    }
                }
            }
            fila.pop();
        }
        if(precede.find(des)!=precede.end())
        {
            pilha.push_back(des);
            while(pilha.back()!=ori)
                pilha.push_back(precede[pilha.back()]);
            for(int i=pilha.size()-1;i>=1;i--)
                soma+=MATRIZ[pilha[i]][pilha[i-1]];
            return soma;
        }
        else
            return -1;
    }
  • Paulo Felipe respondido 5 years ago

    Resposta no Toolkit

    4 5
    1 2 5
    2 1 10
    3 4 8
    4 3 7
    2 3 6
    5
    1 2
    1 3
    1 4
    4 3
    4 1
    3 3
    1 2 10
    2 3 1
    3 2 1
    3
    1 3
    3 1
    3 2
    5 8
    1 2 10
    2 1 5
    1 3 3
    3 1 8
    3 4 15
    4 5 20
    5 4 21
    5 1 7
    11
    3 2
    2 3
    1 2
    2 1
    5 1
    4 1
    1 4
    4 5
    5 4
    1 5
    3 4
    2 1
    1 2 3
    0
    0 0
  • Paulo Felipe respondido 5 years ago

    Olá pessoal, estou implementando o Dijkstra porém está dando Wrong Answer 100%, alguém pode me ajudar?

    #include <iostream>
    #include <list>
    #include <vector>
    #include <map>
    #include <limits>
    #include <algorithm>
    using namespace std;
    map<int, int>custo;
    typedef struct
    {
        map<int, int>lig;
    }vert;
    bool func(int x, int y)
    {
        return custo[x]<custo[y];
    }
    int main()
    {
        vector<vert>vertice;
        vector<int>pilha;
        map<int, int>precede;
        map<int, int>::iterator it;
        list<int>lista;
        list<int>::iterator iter;
        vert vt;
        int v, ar, v1, v2, peso, c, soma = 0;
        while(cin>>v>>ar && (v!=0 || ar!=0))
        {
            for(int i=0;i<v;i++)
                vertice.push_back(vt);
            for(int i=0;i<ar;i++)
            {
                cin>>v1>>v2>>peso;
                vertice[v1-1].lig[v2-1] = peso;
            }
            for(int i=0;i<v;i++)
            {
                for(it=vertice[i].lig.begin();it!=vertice[i].lig.end();it++)
                {
                    if(vertice[it->first].lig.find(i)!=vertice[it->first].lig.end())//ele tem eu!
                    {
                        vertice[i].lig[it->first] = 0;
                        vertice[it->first].lig[i] = 0;
                    }
                }
            }
            cin>>c;
            for(int i=0;i<c;i++)
            {
                cin>>v1>>v2;
                v1--; v2--;
                for(int j=0;j<v;j++)
                {
                    custo[j] = numeric_limits<int>::max();
                    lista.push_back(j);
                }
                custo[v1] = 0;
                while(!lista.empty())
                {
                    iter = min_element(lista.begin(), lista.end(), func);
                    lista.erase(iter);
                    int v = *iter;
                    for(it = vertice[v].lig.begin(); it!=vertice[v].lig.end(); it++)
                    {
                        if(binary_search(lista.begin(), lista.end(), it->first) && custo[it->first]>(custo[v]+it->second))
                        {
                            custo[it->first] = (custo[v]+it->second);
                            precede[it->first] = v;
                        }
                    }
                }
                if(precede.find(v2)!=precede.end())
                {
                    pilha.push_back(v2);
                    while(pilha.back()!=v1)
                        pilha.push_back(precede[pilha.back()]);
                    for(int j=pilha.size()-1;j>0;j--)
                        soma+=vertice[pilha[j]].lig[pilha[j-1]];
                    cout<<soma<<endl;
                }
                else
                    cout<<"Nao e possivel entregar a carta"<<endl;
                pilha.clear(); precede.clear(); soma = 0;
            }
            cout<<endl;
            vertice.clear();
        }
        return 0;
    }

    Casos de testes que implementei

    4 5
    1 2 5
    2 1 10
    3 4 8
    4 3 7
    2 3 6
    5
    1 2
    1 3
    1 4
    4 3
    4 1
    3 3
    1 2 10
    2 3 1
    3 2 1
    3
    1 3
    3 1
    3 2
    5 8
    1 2 10
    2 1 5
    1 3 3
    3 1 8
    3 4 15
    4 5 20
    5 4 21
    5 1 7
    11
    3 2
    2 3
    1 2
    2 1
    5 1
    4 1
    1 4
    4 5
    5 4
    1 5
    3 4
    2 1
    1 2 3
    0
    0 0
  • Aline R Oliveira respondido 6 years ago

    Olá, estou recebendo TLE. Para cada consulta estou recalculando as distâncias e dando a resposta. Devo deixar todas as distâncias pré-calculadas só para consulta mesmo?

  • Bruno Otávio respondido 6 years ago

    Galera, por favor, estou precisando de casos teste par ao meu problema. Está dando apenas 20% WA, mas eu não consigo descobrir o que está errado. Fiz usando Djikstra (código abaixo)... Obrigado!

    #include <bits/stdc++.h>
    using namespace std;
    
    #define INF 1500000
    
    int cidades, acordos;
    int M[501][501];
    long int custo[501];
    int anterior[501];
    bool fechado[501];
    
    void djikstra(int origem)
    {
        int cost, v_dest;
        int vcm; // vcm é o vertice do custo mínimo.
    
        for (int i=1; i<=cidades; i++) {
            fechado[i] = 0;
            anterior[i] = -1;
            custo[i] = INF;
        }
        cout << "";
    
        vcm = origem;
        custo[origem] = 0;
        anterior[origem] = -1;
    
        while (vcm != -1)
        {
            fechado[vcm] = 1;
            for (int i=1; i<=cidades; i++)
            {
                if (M[vcm][i] != INF)
                {
                    cost = M[vcm][i];
                    v_dest = i;
                }
    
                if ((custo[v_dest]) > (custo[vcm]+cost))
                {
                    custo[v_dest] = custo[vcm]+cost;
                    anterior[v_dest] = vcm;
                }
            }
    
            vcm = -1;
            cost = INF;
            for (int i=1; i<=cidades; i++)
            {
                if ((!fechado[i]) && (cost > custo[i]))
                {
                    cost = custo[i];
                    vcm = i;
                }
            }
        }
    }
    
    int main()
    {
        ios::sync_with_stdio(0);
        int x, y, h;
    
        cin >> cidades >> acordos;
        while (cidades && acordos)
        {
            for (int i=0; i<=cidades; i++)
                for (int j=0; j<=cidades; j++)
                    M[i][j] = INF;
    
            for (int i=0; i<acordos; i++)
            {
                cin >> x >> y >> h;
    
                if (M[y][x] != INF)
                {
                    M[x][y] = 0;
                    M[y][x] = 0;
                }
                else
                    M[x][y] = h;
            }
    
            int origem, destino, consultas;
            cin >> consultas;
            for (int i=0; i<consultas; i++)
            {
                cin >> origem >> destino;
                cout << "";
                djikstra(origem);
                if (custo[destino] != INF)
                    cout << "" << custo[destino] << "\n";
                else
                    cout << "Nao e possivel entregar a carta\n";
            }
    
            cout << "\n";
            cin >> cidades >> acordos;
        }
    
        return 0;
    }
  • William Almeida Suzukayama respondido 6 years ago

    Só presentation error :\ . Já resolvi.

  • Denis Costa respondido 6 years ago

    Era isso mesmo. Muito obrigado!!!

    MOD
  • André Alves respondido 6 years ago

    Seu erro tá dentro desse if:

    if (distance[j] < shortest_distance && !correct[j])

    Você quer pegar o vértice com a menor distância até o momento, você não pode ter esse break pois seu vetor não é ordenado.

    Uma dica também, caso o próximo vértice a ser visitado seja o destino, você não precisa continuar a exploração do grafo, pois já é garantido que você encontrou o menor caminho até ele.

  • Denis Costa respondido 6 years ago

    Alguém?

    MOD