Олимпиадный тренинг

Задача 27268. Ford-Bellman: The Beginning (C++)

Задача

Complete the program so that it correctly solves the following problem.

Given a directed graph that can have multiple edges and loops. Each edge has a weight expressed as an integer (possibly negative). It is guaranteed that there are no negative weight cycles.

You need to calculate the lengths of the shortest paths from vertex number 1 to all other vertices.

Input

The program first receives the number N (1 <= N <= 100) – the number of graph vertices and the number M (0 <= M <= 10000) – number of ribs. The following lines contain M of triples of numbers describing the edges: the beginning of the edge, the end of the edge, and the weight (weight – is an integer from -100 to 100).

Output

The program should output N numbers – distances from vertex number 1 to all vertices of the graph. If there is no path to the corresponding vertex, print the number 30000 instead of the length of the path.

Examples

#	Input	Output
1	6 4 1 2 10 2 3 10 1 3 100 4 5 -10	0 10 20 30000 30000 30000

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Ваш ответ

C++

Напишите программу ниже
#include <iostream> #include <vector> using namespace std; const int INF = 1e9; struct edge { int from, to, w; }; vector <edge> edges; int d[201]; int main() { int n, m, from, to, w; cin >> n >> m; for (int i = 1; i <= n; i++) { d[i] = INF; } for (int i = 0; i < m; i++) { edge e; cin >> e.from >> e.to >> e.w; edges.push_back(e); } d[1] = 0; for (int i = 1; i < n; i++) {

} for (int i = 1; i <= n; i++) { if (d[i] == INF) cout << 30000 <<" " ; else cout << d[i] << " "; } return 0; }

Напишите программу ниже

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

struct edge
{
    int from, to, w;
};

vector <edge> edges;
int d[201];

int main()
{
    int n, m, from, to, w;

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < m; i++)
    {
      edge e;
        cin >> e.from >> e.to >> e.w;
        edges.push_back(e);
    }

    d[1] = 0;

    for (int i = 1; i < n; i++)
    {

 }

    for (int i = 1; i <= n; i++)
    {
        if (d[i] == INF)
            cout << 30000 <<" " ;
        else
            cout << d[i] << " ";
    }

    return 0;
}

Загруженные файлы

Нет