作者darrenlee1 (darrenleeleelee)
看板C_and_CPP
標題[討論] Dijkstra UVa-10986 Sending Email
時間Sat Jun 13 18:06:23 2020
抱歉又來打擾大家，這題明顯是Dijkstra，我交上去是過的。
但我再跑Udebug(intput 是Batman那個) 卻有21個不相同。
我想了一陣子，還是沒找到問題，希望大家能幫我看一下。
udebug :
https://www.udebug.com/UVa/10986
這是我的code
#include <bits/stdc++.h>
using namespace std;
int n, m ,S, T;
int w[20010][20010], dis[20010];
vector<int> v[20000+10];
struct Node
{
int node, weight;
Node(int _n, int _w){
node = _n;
weight = _w;
}
bool operator<(Node const other)const{
return weight > other.weight;
}
};
void dijsktra(int src)
{
priority_queue<Node> pq;
pq.push(Node(src, 0));
while(!pq.empty())
{
auto top = pq.top();
pq.pop();
if(dis[top.node] != 1e9) continue;
dis[top.node] = top.weight;
for(auto i : v[top.node]){
if(dis[i] == 1e9) pq.push(Node(i, top.weight + w[top.node][i]));
}
}
}
int main(int argc, char const *argv[])
{
int N, cnt = 1, temp1, temp2, tempw;
cin >> N;
while(N--){
cin >> n >> m >> S >> T;
for(int i = 0; i < n; i++)
{
v[i].clear();
dis[i] = 1e9;
}
while(m--)
{
cin >> temp1 >> temp2 >> tempw;
v[temp1].push_back(temp2);
v[temp2].push_back(temp1);
w[temp1][temp2] = w[temp2][temp1] = tempw;
}
dijsktra(S);
if(dis[T] != 1e9) printf("Case #%d: %d\n", cnt++, dis[T]);
else printf("Case #%d: unreachable\n", cnt++);
}
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.141.64.159 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1592042786.A.DD9.html
1F：→ a58524andy: 你的dijkstra好像有點…特別(?06/13 19:34
2F：→ a58524andy: 要更新的點不是只有無限遠的06/13 19:37
3F：→ darrenlee1: 對 但我一開始都設成無限遠06/13 19:38
4F：推 firejox: 同一樓，你這不是Dijkstra06/14 13:35
5F：→ firejox: 簡單反例是ABC三點皆相鄰，起點A終點C，AC > AB + BC06/14 13:39
6F：→ darrenlee1: 但我每次都是目前能延伸最短的路徑，假如AC>AB>BC 最06/14 14:11
7F：→ darrenlee1: 短路徑不會是AC這條邊06/14 14:11
8F：→ a58524andy: 測資有zero edge，假設現在兩點A B跟Source都是1006/14 14:19
9F：→ a58524andy: 同時AC = 1、BC = 0，你的queue剛好先掃A的話06/14 14:19
10F：→ a58524andy: 那麼C不會被更新成S -> B -> C這個距離1006/14 14:20
11F：→ a58524andy: 而是會卡在S -> A -> C這個1106/14 14:20
12F：→ a58524andy: *並且假設AB=006/14 14:20
13F：→ a58524andy: 恩我在說甚麼@@ 這跟zero edge也沒什麼關係06/14 14:23
14F：→ a58524andy: 總之當SA=SB=10、AC=m、BC=n、queue剛好先選A來跑 06/14 14:25
15F：→ a58524andy: 並且m>n的時候06/14 14:25
16F：→ a58524andy: 這個寫法應該會出事06/14 14:25
17F：→ chengweihsu: 感覺是input處理有問題，他好像沒說頂點間的邊數<=106/14 15:07
18F：→ chengweihsu: 你用adjacent matrix存邊的權重，如果同一對頂點06/14 15:07
19F：→ chengweihsu: (u,v)有>=兩條邊，你只會紀錄最後輸入的那條，但那06/14 15:07
20F：→ chengweihsu: 條可能比之前記的w[u][v]還大，這樣你等於是在錯的06/14 15:07
21F：→ chengweihsu: 圖上跑dijkstra06/14 15:07
22F：→ a58524andy: 測了一下，樓上應該是對的 06/14 15:32
23F：→ darrenlee1: 他有重複的邊的話我應該把他都加起來在跑dijktra 嗎06/14 20:15
24F：→ darrenlee1: 我改成用+= 還是有點問題欸 還是是我理解有問題06/14 20:24
25F：→ darrenlee1: 我有先清成006/14 20:25
26F：→ darrenlee1: 回一下a大，我是用pq每次會幫我把最小的pop out出來，06/14 20:30
27F：→ darrenlee1: 所以一開始push (SA 10)(SB 10) 先把SA，pop out出來06/14 20:30
28F：→ darrenlee1: 後會push(AC 10+m)，所以接下來pop out的會是SB，因06/14 20:30
29F：→ darrenlee1: 此m<n也不會有問題06/14 20:30
30F：→ chengweihsu: 有重複邊的話你處理input時，要多加條件判斷而不是06/14 20:55
31F：→ chengweihsu: 加起來，因為你最短路徑一定是選所有連接(u,v)的邊06/14 20:55
32F：→ chengweihsu: 中最短的06/14 20:55
33F：→ chengweihsu: 若路徑包含(u,v)這兩點06/14 20:56
34F：→ darrenlee1: 謝謝～過了06/14 21:00
35F：→ darrenlee1: 謝謝大家的幫忙06/14 21:00
※ 編輯: darrenlee1 (220.141.64.159 臺灣), 06/14/2020 21:02:02