[討論] Dijkstra UVa-10986 Sending Email

看板C_and_CPP作者 (darrenleeleelee)時間4年前 (2020/06/13 18:06), 4年前編輯推噓1(1推 0噓 34→)
留言35則, 4人參與, 4年前最新討論串1/1
抱歉又來打擾大家，這題明顯是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://www.ptt.cc/bbs/C_and_CPP/M.1592042786.A.DD9.html
→
06/13 19:34, 4年前 , 1F
你的dijkstra好像有點…特別(?
06/13 19:34, 1F
→
06/13 19:37, 4年前 , 2F
要更新的點不是只有無限遠的
06/13 19:37, 2F
→
06/13 19:38, 4年前 , 3F
對 但我一開始都設成無限遠
06/13 19:38, 3F
推
06/14 13:35, 4年前 , 4F
同一樓，你這不是Dijkstra
06/14 13:35, 4F
→
06/14 13:39, 4年前 , 5F
簡單反例是ABC三點皆相鄰，起點A終點C，AC > AB + BC
06/14 13:39, 5F
→
06/14 14:11, 4年前 , 6F
但我每次都是目前能延伸最短的路徑，假如AC>AB>BC 最
06/14 14:11, 6F
→
06/14 14:11, 4年前 , 7F
短路徑不會是AC這條邊
06/14 14:11, 7F
→
06/14 14:19, 4年前 , 8F
測資有zero edge，假設現在兩點A B跟Source都是10
06/14 14:19, 8F
→
06/14 14:19, 4年前 , 9F
同時AC = 1、BC = 0，你的queue剛好先掃A的話
06/14 14:19, 9F
→
06/14 14:20, 4年前 , 10F
那麼C不會被更新成S -> B -> C這個距離10
06/14 14:20, 10F
→
06/14 14:20, 4年前 , 11F
而是會卡在S -> A -> C這個11
06/14 14:20, 11F
→
06/14 14:20, 4年前 , 12F
*並且假設AB=0
06/14 14:20, 12F
→
06/14 14:23, 4年前 , 13F
恩我在說甚麼@@ 這跟zero edge也沒什麼關係
06/14 14:23, 13F
→
06/14 14:25, 4年前 , 14F
總之當SA=SB=10、AC=m、BC=n、queue剛好先選A來跑
06/14 14:25, 14F
→
06/14 14:25, 4年前 , 15F
並且m>n的時候
06/14 14:25, 15F
→
06/14 14:25, 4年前 , 16F
這個寫法應該會出事
06/14 14:25, 16F
→
06/14 15:07, 4年前 , 17F
感覺是input處理有問題，他好像沒說頂點間的邊數<=1
06/14 15:07, 17F
→
06/14 15:07, 4年前 , 18F
你用adjacent matrix存邊的權重，如果同一對頂點
06/14 15:07, 18F
→
06/14 15:07, 4年前 , 19F
(u,v)有>=兩條邊，你只會紀錄最後輸入的那條，但那
06/14 15:07, 19F
→
06/14 15:07, 4年前 , 20F
條可能比之前記的w[u][v]還大，這樣你等於是在錯的
06/14 15:07, 20F
→
06/14 15:07, 4年前 , 21F
圖上跑dijkstra
06/14 15:07, 21F
→
06/14 15:32, 4年前 , 22F
測了一下，樓上應該是對的
06/14 15:32, 22F
→
06/14 20:15, 4年前 , 23F
他有重複的邊的話我應該把他都加起來在跑dijktra 嗎
06/14 20:15, 23F
→
06/14 20:24, 4年前 , 24F
我改成用+= 還是有點問題欸 還是是我理解有問題
06/14 20:24, 24F
→
06/14 20:25, 4年前 , 25F
我有先清成0
06/14 20:25, 25F
→
06/14 20:30, 4年前 , 26F
回一下a大，我是用pq每次會幫我把最小的pop out出來，
06/14 20:30, 26F
→
06/14 20:30, 4年前 , 27F
所以一開始push (SA 10)(SB 10) 先把SA，pop out出來
06/14 20:30, 27F
→
06/14 20:30, 4年前 , 28F
後會push(AC 10+m)，所以接下來pop out的會是SB，因
06/14 20:30, 28F
→
06/14 20:30, 4年前 , 29F
此m<n也不會有問題
06/14 20:30, 29F
→
06/14 20:55, 4年前 , 30F
有重複邊的話你處理input時，要多加條件判斷而不是
06/14 20:55, 30F
→
06/14 20:55, 4年前 , 31F
加起來，因為你最短路徑一定是選所有連接(u,v)的邊
06/14 20:55, 31F
→
06/14 20:55, 4年前 , 32F
中最短的
06/14 20:55, 32F
→
06/14 20:56, 4年前 , 33F
若路徑包含(u,v)這兩點
06/14 20:56, 33F
→
06/14 21:00, 4年前 , 34F
謝謝～過了
06/14 21:00, 34F
→
06/14 21:00, 4年前 , 35F
謝謝大家的幫忙
06/14 21:00, 35F
※ 編輯: darrenlee1 (220.141.64.159 臺灣), 06/14/2020 21:02:02
‣ 更多 darrenlee1 的文章
文章代碼(AID): #1UvAKYtP (C_and_CPP)