• Posible flujo de trabajo
• Problemas sobre Graph Algorithms
  • Problemas resueltos en clase

Posible flujo de trabajo

• descargar el archivo .zip de el problema de el Jutge.org que se quiere resolver
• unzip el archivo
• en la carpeta obtenida teneis:
  • un file .pdf con el enunciado del problema,
  • uno o más files de texto con ejemplos de input sample.inp
  • los correspondiente outputs correctos sample.cor
• crear un file con el vuestro codigo sorgente C++ para resolver el problema
• compilar el codigo sorgente con g++ -std=c++11.
  Posibles flags utiles: -Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG
• testar el ejecutable en los ejemplos:
  por ejemplo con ./a.out < sample.inp > output
• testar que el file de output sea correcto:
  por ejemplo con diff output sample.cor
• una vez que estais convencidos que vuestra solucion es correcta, enviarla al Jutge
  • no enviar al Jutge soluciones que no sean correctas en los ejemplos que teneis!
  • no intentar re-escribir a mano los ejemplos de input

Problemas sobre Graph Algorithms

Los problemas de el apartado EDA Curs 2023/2024 Q2 \(\rightarrow\) Graph algorithms.

Dijkstra’s Algorithm
P43859 Weighted shortest path (1)
P13994 Weighted shortest path (2)
P25235 Weighted shortest path (3)
P39586 Weighted shortest path (4)

Minimum Spanning Trees
P12887 Minimum spanning trees

= the problem might be harder than the rest

Problemas resueltos en clase

P43859 Weighted shortest path (1)

To experiment with runs of Dijkstra Shortest Path

//Weighted Shortest path - 1
// Basic Dijkstra
#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>

using namespace std;

struct Edge {
    int v, c;
    Edge(int vv, int cc) : v(vv), c(cc) {}
};

using P = pair<int,int>; //distance, vertex
using VVP = vector<vector<Edge>>;

vector<int> dijkstra(const VVP& g, int s){
 // here goes dijkstra
} 

int main(){
    int n, m;
    while(cin >> n >> m){
        VVP g(n);
        for (int k = 0; k < m; ++k){
            int u, v, c;
            cin >> u >> v >> c;
            g[u].push_back(Edge(v,c));
        }
        int x, y;
        cin >> x >> y;
        vector<int> d = dijkstra(g, x);
        if (d[y] == INT_MAX) cout << "no path from " << x << " to " << y << endl;
        else cout << d[y] << endl;
    }
}