[討論] Dijkstra UVa-10986 Sending Email

[darrenlee1 (darrenleeleelee)]

抱歉又來打擾大家，這題明顯是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
→ a58524andy: 你的dijkstra好像有點…特別(?
→ a58524andy: 要更新的點不是只有無限遠的
→ darrenlee1: 對 但我一開始都設成無限遠
推 firejox: 同一樓，你這不是Dijkstra
→ firejox: 簡單反例是ABC三點皆相鄰，起點A終點C，AC > AB + BC
→ darrenlee1: 但我每次都是目前能延伸最短的路徑，假如AC>AB>BC 最
→ darrenlee1: 短路徑不會是AC這條邊
→ a58524andy: 測資有zero edge，假設現在兩點A B跟Source都是10
→ a58524andy: 同時AC = 1、BC = 0，你的queue剛好先掃A的話
→ a58524andy: 那麼C不會被更新成S -> B -> C這個距離10
→ a58524andy: 而是會卡在S -> A -> C這個11
→ a58524andy: *並且假設AB=0
→ a58524andy: 恩我在說甚麼@@ 這跟zero edge也沒什麼關係
→ a58524andy: 總之當SA=SB=10、AC=m、BC=n、queue剛好先選A來跑
→ a58524andy: 並且m>n的時候
→ a58524andy: 這個寫法應該會出事
→ chengweihsu: 感覺是input處理有問題，他好像沒說頂點間的邊數<=1
→ chengweihsu: 你用adjacent matrix存邊的權重，如果同一對頂點
→ chengweihsu: (u,v)有>=兩條邊，你只會紀錄最後輸入的那條，但那
→ chengweihsu: 條可能比之前記的w[u][v]還大，這樣你等於是在錯的
→ chengweihsu: 圖上跑dijkstra
→ a58524andy: 測了一下，樓上應該是對的
→ darrenlee1: 他有重複的邊的話我應該把他都加起來在跑dijktra 嗎
→ darrenlee1: 我改成用+= 還是有點問題欸 還是是我理解有問題
→ darrenlee1: 我有先清成0
→ darrenlee1: 回一下a大，我是用pq每次會幫我把最小的pop out出來，
→ darrenlee1: 所以一開始push (SA 10)(SB 10) 先把SA，pop out出來
→ darrenlee1: 後會push(AC 10+m)，所以接下來pop out的會是SB，因
→ darrenlee1: 此m<n也不會有問題
→ chengweihsu: 有重複邊的話你處理input時，要多加條件判斷而不是
→ chengweihsu: 加起來，因為你最短路徑一定是選所有連接(u,v)的邊
→ chengweihsu: 中最短的
→ chengweihsu: 若路徑包含(u,v)這兩點
→ darrenlee1: 謝謝～過了
→ darrenlee1: 謝謝大家的幫忙
※ 編輯: darrenlee1 (220.141.64.159 臺灣), 06/14/2020 21:02:02