Algo lab/dijkstra - ประวัติรุ่นแก้ไข

Jittat: /* Fast version (new) */

2026-02-16T06:42:52Z

Fast version (new)

Jittat เมื่อ 05:08, 16 กุมภาพันธ์ 2569

2026-02-16T05:08:00Z

Jittat เมื่อ 08:14, 29 มกราคม 2567

2024-01-29T08:14:23Z

Jittat: สร้างหน้าด้วย "== Slower version == #include #include using namespace std; const int MAX_N = 1000010; vector ad..."

2023-10-16T06:53:47Z

สร้างหน้าด้วย "== Slower version == <syntaxhighlight lang="cpp"> #include <iostream> #include <vector> using namespace std; const int MAX_N = 1000010; vector<int> ad..."

หน้าใหม่

== Slower version ==
<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 1000010;

vector<int> adj[MAX_N];
vector<int> weights[MAX_N];

int n,m;
int deg[MAX_N];
void read_input()
{
cin >> n >> m;
for(int i=0; i<n; i++) {
deg[i] = 0;
}

for(int i=0; i<m; i++) {
int a,b,w;

cin >> a >> b >> w;
a--; b--;

adj[a].push_back(b);
weights[a].push_back(w);
deg[a]++;

adj[b].push_back(a);
weights[b].push_back(w);
deg[b]++;
}
}

bool is_visited[MAX_N];
int D[MAX_N];
const int INFINITY = 1000000000;

void dijkstra(int s)
{
for(int i=0; i<n; i++) {
is_visited[i] = false;
D[i] = INFINITY;
}

D[s] = 0;

for(int i=0; i<n; i++) {
// find u with minimum D[u] such that is_visited[u] = false
int u = -1;
int du = INFINITY;
for(int x=0; x<n; x++) {
if((!is_visited[x]) && (D[x] < du)) {
u = x;
du = D[x];
}
}

//cout << u << " - " << du << endl;

for(int j=0; j<deg[u]; j++) {
int v = adj[u][j]; // edge (u,v)
int w = weights[u][j];

//cout << D[u] << " " << w << " " << D[v] << endl;
if(D[u] + w < D[v]) {
D[v] = D[u] + w;
}
}
is_visited[u] = true;
}

}

int main()
{
read_input();
dijkstra(0);
cout << D[n-1] << endl;
}
</syntaxhighlight>

== Fast version ==
<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int MAX_N = 1000010;

vector<int> adj[MAX_N];
vector<int> weights[MAX_N];

int n,m;
int deg[MAX_N];
void read_input()
{
cin >> n >> m;
for(int i=0; i<n; i++) {
deg[i] = 0;
}

for(int i=0; i<m; i++) {
int a,b,w;

cin >> a >> b >> w;
a--; b--;

adj[a].push_back(b);
weights[a].push_back(w);
deg[a]++;

adj[b].push_back(a);
weights[b].push_back(w);
deg[b]++;
}
}

bool is_visited[MAX_N];
int D[MAX_N];
const int INFINITY = 1000000000;

void dijkstra(int s)
{
for(int i=0; i<n; i++) {
is_visited[i] = false;
D[i] = INFINITY;
}

D[s] = 0;
set<pair<int,int>> Q;
Q.insert(make_pair(0,s));

for(int i=0; i<n; i++) {
int u;

do {
if(Q.empty())
return;
pair<int,int> uu = *(Q.begin());
Q.erase(Q.begin());
u = uu.second;
} while(is_visited[u]);

for(int j=0; j<deg[u]; j++) {
int v = adj[u][j]; // edge (u,v)
int w = weights[u][j];

//cout << D[u] << " " << w << " " << D[v] << endl;
if(D[u] + w < D[v]) {
D[v] = D[u] + w;

Q.insert(make_pair(D[v],v));
}
}
is_visited[u] = true;
}

}

int main()
{
read_input();
dijkstra(0);
cout << D[n-1] << endl;
}
</syntaxhighlight>

@@ แถว 83: / แถว 83: @@
+}
 </syntaxhighlight>
 == Fast version (new) ==

@@ แถว 55: / แถว 55: @@
      for(int x=0; x<n; x++) {
        if((!is_visited[x]) && (D[x] < du)) {
-	u = x;
+        u = x;
-	du = D[x];
+        du = D[x];
+       }
+     }
@@ แถว 68: / แถว 68: @@
        //cout << D[u] << " " << w << " " << D[v] << endl;
        if(D[u] + w < D[v]) {
-	D[v] = D[u] + w;
+        D[v] = D[u] + w;
+       }
+     }
@@ แถว 141: / แถว 141: @@
        int v = adj[u][dd];
        if(d[v] > d[u] + weights[u][dd]) {
-	d[v] = d[u] + weights[u][dd];
+        d[v] = d[u] + weights[u][dd];
-	Q.insert(make_pair(d[v],v));
+        Q.insert(make_pair(d[v],v));
+       }
+     }
@@ แถว 214: / แถว 214: @@
      do {
        if(Q.empty())
-	return;
+        return;
        pair<int,int> uu = *(Q.begin());
        Q.erase(Q.begin());
@@ แถว 226: / แถว 226: @@
        //cout << D[u] << " " << w << " " << D[v] << endl;
        if(D[u] + w < D[v]) {
-	D[v] = D[u] + w;
+        D[v] = D[u] + w;
-	Q.insert(make_pair(D[v],v));
+        Q.insert(make_pair(D[v],v));
+       }
+     }

@@ แถว 84: / แถว 84: @@
 </syntaxhighlight>
-== Fast version ==
+== Fast version (new) ==
 <syntaxhighlight lang="cpp">
 #include <iostream>