作者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/cn.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