[討論] Dijkstra UVa-10986 Sending Email
抱歉又來打擾大家,這題明顯是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,
3年前
, 1F
06/13 19:34, 1F
→
06/13 19:37,
3年前
, 2F
06/13 19:37, 2F
→
06/13 19:38,
3年前
, 3F
06/13 19:38, 3F
推
06/14 13:35,
3年前
, 4F
06/14 13:35, 4F
→
06/14 13:39,
3年前
, 5F
06/14 13:39, 5F
→
06/14 14:11,
3年前
, 6F
06/14 14:11, 6F
→
06/14 14:11,
3年前
, 7F
06/14 14:11, 7F
→
06/14 14:19,
3年前
, 8F
06/14 14:19, 8F
→
06/14 14:19,
3年前
, 9F
06/14 14:19, 9F
→
06/14 14:20,
3年前
, 10F
06/14 14:20, 10F
→
06/14 14:20,
3年前
, 11F
06/14 14:20, 11F
→
06/14 14:20,
3年前
, 12F
06/14 14:20, 12F
→
06/14 14:23,
3年前
, 13F
06/14 14:23, 13F
→
06/14 14:25,
3年前
, 14F
06/14 14:25, 14F
→
06/14 14:25,
3年前
, 15F
06/14 14:25, 15F
→
06/14 14:25,
3年前
, 16F
06/14 14:25, 16F
→
06/14 15:07,
3年前
, 17F
06/14 15:07, 17F
→
06/14 15:07,
3年前
, 18F
06/14 15:07, 18F
→
06/14 15:07,
3年前
, 19F
06/14 15:07, 19F
→
06/14 15:07,
3年前
, 20F
06/14 15:07, 20F
→
06/14 15:07,
3年前
, 21F
06/14 15:07, 21F
→
06/14 15:32,
3年前
, 22F
06/14 15:32, 22F
→
06/14 20:15,
3年前
, 23F
06/14 20:15, 23F
→
06/14 20:24,
3年前
, 24F
06/14 20:24, 24F
→
06/14 20:25,
3年前
, 25F
06/14 20:25, 25F
→
06/14 20:30,
3年前
, 26F
06/14 20:30, 26F
→
06/14 20:30,
3年前
, 27F
06/14 20:30, 27F
→
06/14 20:30,
3年前
, 28F
06/14 20:30, 28F
→
06/14 20:30,
3年前
, 29F
06/14 20:30, 29F
→
06/14 20:55,
3年前
, 30F
06/14 20:55, 30F
→
06/14 20:55,
3年前
, 31F
06/14 20:55, 31F
→
06/14 20:55,
3年前
, 32F
06/14 20:55, 32F
→
06/14 20:56,
3年前
, 33F
06/14 20:56, 33F
→
06/14 21:00,
3年前
, 34F
06/14 21:00, 34F
→
06/14 21:00,
3年前
, 35F
06/14 21:00, 35F
※ 編輯: darrenlee1 (220.141.64.159 臺灣), 06/14/2020 21:02:02