Đề bài

Cho đồ thị có hướng có trọng số không âm G=<V,E> được biểu diễn dưới dạng danh sách cạnh trọng số. Hãy viết chương trình tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị. Dữ liệu đảm bảo có đường đi từ đỉnh S tới mọi đỉnh khác trên đồ thị.

Input

  • Dòng đầu tiên chứa 3 số n, m, s là số đỉnh, số cạnh của đồ thị và đỉnh bắt đầu (1 <= n <= 1000, 1 <= m <= n*(n-1)/2).
  • M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n).
  • Ràng buộc: 1 <= n <= 1000; 1 <= m <= n*(n-1)/2; Trọng số các cạnh là số nguyên không âm không vượt quá 100;

Output

  • Ghi ra file văn bản lab_t_output.OUT gồm đường đi ngắn nhất từ đỉnh S đến các đỉnh còn lại.

Sample 1

Input Output
10 44 5
7 5 60
9 8 31
9 1 83
4 3 25
6 2 1
4 1 52
6 3 76
7 6 95
9 7 84
8 2 91
10 7 8
6 4 32
10 2 76
3 1 62
10 6 88
8 3 12
5 3 15
5 4 40
9 2 20
3 2 5
5 1 36
9 4 98
8 6 65
8 5 95
10 3 55
9 6 95
10 1 5
4 2 70
7 1 80
10 4 35
7 2 99
10 9 24
6 5 94
2 1 77
8 1 12
8 4 76
9 3 27
5 2 5
9 5 12
10 5 1
8 7 59
6 1 1
10 8 92
7 3 54
6 5 10 35 0 6 9 18 12 1

Sample 2

Input Output
6 8 1
1 2 7
1 3 12
2 3 2
2 4 9
3 5 10
4 6 1
5 4 4
5 6 5
0 7 9 16 19 17

Giải

  • Source code:
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
using ll = long long;
const int maxN = 100001;
const int INF = 1e9; // so vo cung
int n, m; // n: so dinh, m: so canh
int s; // dinh bat dau
vector<pair<int, int>> adj[maxN]; // vector luu tru canh co trong so
void inp() {
cin >> n >> m >> s;
for(int i = 0; i < m; i++) {
int x, y, w; // canh x -> y co trong so w
cin >> x >> y >> w;
adj[x].push_back({y, w});
// Do thi co huong thi comment dong code sau
//adj[y].push_back({x, w});
}
}
void dijkstra(int s) {
// Mang luu khoang cach duong di
vector<ll> d(n+1, INF);
d[s] = 0;
// Hang doi uu tien
// {khoang_cach, dinh}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
Q.push({0, s}); // Khoi tao
while(!Q.empty()) {
// Chon ra dinh co khoang cach tu s nho nhat
pair<int, int> top = Q.top();
Q.pop();
int u = top.second;
int kc = top.first;
if(kc > d[u])
continue;
// Relaxation: cap nhat khoang cach tu s cho toi moi dinh ke voi u
for(auto it: adj[u]) {
int v = it.first;
int w = it.second;
if(d[v] > d[u] + w) {
d[v] = d[u] + w;
Q.push({d[v], v});
}
}
}
for(int i = 1; i <= n; i++) {
cout << d[i] << ' ';
}
}
int main() {
// Chuyen NHAP, XUAT thanh file
freopen("lab_5_input.INP", "r", stdin);
freopen("lab_5_output.OUT", "w", stdout);
// INPUT
inp();
// OUTPUT
dijkstra(s);
}
#include<bits/stdc++.h> #include<iostream> using namespace std; using ll = long long; const int maxN = 100001; const int INF = 1e9; // so vo cung int n, m; // n: so dinh, m: so canh int s; // dinh bat dau vector<pair<int, int>> adj[maxN]; // vector luu tru canh co trong so void inp() { cin >> n >> m >> s; for(int i = 0; i < m; i++) { int x, y, w; // canh x -> y co trong so w cin >> x >> y >> w; adj[x].push_back({y, w}); // Do thi co huong thi comment dong code sau //adj[y].push_back({x, w}); } } void dijkstra(int s) { // Mang luu khoang cach duong di vector<ll> d(n+1, INF); d[s] = 0; // Hang doi uu tien // {khoang_cach, dinh} priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q; Q.push({0, s}); // Khoi tao while(!Q.empty()) { // Chon ra dinh co khoang cach tu s nho nhat pair<int, int> top = Q.top(); Q.pop(); int u = top.second; int kc = top.first; if(kc > d[u]) continue; // Relaxation: cap nhat khoang cach tu s cho toi moi dinh ke voi u for(auto it: adj[u]) { int v = it.first; int w = it.second; if(d[v] > d[u] + w) { d[v] = d[u] + w; Q.push({d[v], v}); } } } for(int i = 1; i <= n; i++) { cout << d[i] << ' '; } } int main() { // Chuyen NHAP, XUAT thanh file freopen("lab_5_input.INP", "r", stdin); freopen("lab_5_output.OUT", "w", stdout); // INPUT inp(); // OUTPUT dijkstra(s); }
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
using ll = long long;

const int maxN = 100001;
const int INF = 1e9; // so vo cung

int n, m; // n: so dinh, m: so canh
int s; // dinh bat dau
vector<pair<int, int>> adj[maxN]; // vector luu tru canh co trong so

void inp() {
  cin >> n >> m >> s;
  for(int i = 0; i < m; i++) {
    int x, y, w; // canh x -> y co trong so w
    cin >> x >> y >> w;
    adj[x].push_back({y, w});
    
    // Do thi co huong thi comment dong code sau
    //adj[y].push_back({x, w});
  }
}

void dijkstra(int s) {
  // Mang luu khoang cach duong di
  vector<ll> d(n+1, INF);
  d[s] = 0;
  
  // Hang doi uu tien
  // {khoang_cach, dinh}
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
  Q.push({0, s}); // Khoi tao
  while(!Q.empty()) {
    // Chon ra dinh co khoang cach tu s nho nhat
    pair<int, int> top = Q.top();
    Q.pop();
    
    int u = top.second;
    int kc = top.first;
    if(kc > d[u])
      continue;
      
    // Relaxation: cap nhat khoang cach tu s cho toi moi dinh ke voi u
    for(auto it: adj[u]) {
      int v = it.first;
      int w = it.second;
      if(d[v] > d[u] + w) {
        d[v] = d[u] + w;
        Q.push({d[v], v});
      }
    }
  }
  
  for(int i = 1; i <= n; i++) {
    cout << d[i] << ' ';
  }
}

int main() {
  // Chuyen NHAP, XUAT thanh file
  freopen("lab_5_input.INP", "r", stdin);
  freopen("lab_5_output.OUT", "w", stdout);

  // INPUT
  inp();
  
  // OUTPUT
  dijkstra(s);
}