求助，#3,#4WA，看了下数据，错了几个点

liuye11 @ 2022-05-28 20:48:06

#include<bits/stdc++.h>
#define maxn 500005
#define MYINF -1
using namespace std;
class Seg {
public:
    int length, to;
    Seg* next;
    Seg(int to1, int length1) {
        next = NULL;
        length = length1;
        to = to1;
    }
};
class Node {
public:
    //  int count;
    Seg* head;
    Seg* tail;
    Node() {
        head = NULL;
        tail = NULL;
    }
    void addSeg(Seg* seg) {
        if (head == NULL) {
            head = seg;
            tail = seg;
        }
        else {
            tail->next = seg;
            tail = seg;
        }
    }
};
int bag[maxn];
bool inQue[maxn];
Node node[maxn];
int n, a, b, c, d;
int start, target;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;

//void shuRu1() {
//  ifstream ifstr("map2.txt");
//  ifstr >> n >> c >> start;
//  Seg* seg;
//  for (int i = 1; i <= c; i++) {
//      ifstr >> a >> b >> d;
//      if (a == b) {
//          continue;
//      }
//      seg = new Seg(b, d);
//      node[a].addSeg(seg);
//  }
//  ifstr.close();
//}
void shuRu2() {
    Seg* seg;
    cin >> n >> c >> start;
    for (int i = 1; i <= c; i++) {
        cin >> a >> b >> d;
        if (a == b) {
            continue;
        }
        else {
            seg = new Seg(b, d);
            node[a].addSeg(seg);
        }
    }
}
void bianli(int n) {
    if (node[n].head == NULL) {
        return;
    }
    Seg* seg = node[n].head;
    inQue[n] = 1;
    if (n == start) {
        do {
            a = seg->length;
            bag[seg->to] = a;
            que.push(make_pair(a, seg->to));
            seg = seg->next;
        } while (seg != NULL);
        return;
    }
    else {
        do {

            a = seg->length;
            if (bag[seg->to] == MYINF) {
                bag[seg->to] = bag[n] + a;
            }
            else {
                if (bag[n] + a < bag[seg->to]) {
                    bag[seg->to] = bag[n] + a;
                }
            }
            if (!inQue[seg->to]) {
                que.push(make_pair(bag[seg->to], seg->to));
            }
            seg = seg->next;
        } while (seg != NULL);
    }

}
int main() {
    memset(bag, MYINF, sizeof(bag));
    shuRu2();
    //  shuRu1();
//  ofstream of("out.txt");
    bianli(start);
    bag[start] = 0;
    while (!que.empty())
    {
        if (!inQue[que.top().second]) {
            bianli(que.top().second);
        }
        que.pop();
    }
    for (int i = 1; i <= n; i++) {
        cout << bag[i] << " ";
        //          of<<"i:"<<i<<"::"<<bag[i]<<" ";
    }
    return 0;
}

by liuye11 @ 2022-05-28 22:29:28

重复执行了两次遍历，AC了，这是为什么？？？

#include<bits/stdc++.h>
#define maxn 500005
#define MYINF -1
using namespace std;
class Seg {
public:
    int length, to;
    Seg* next;
    Seg(int to1, int length1) {
        next = NULL;
        length = length1;
        to = to1;
    }
};
class Node {
public:
    //  int count;
    Seg* head;
    Seg* tail;
    Node() {
        head = NULL;
        tail = NULL;
    }
    void addSeg(Seg* seg) {
        if (head == NULL) {
            head = seg;
            tail = seg;
        }
        else {
            tail->next = seg;
            tail = seg;
        }
    }
};
int bag[maxn];
bool inQue[maxn];
Node node[maxn];
int luJing[maxn]; 
int n, a, b, c, d;
int start, target;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;

//void shuRu1() {
//  ifstream ifstr("map2.txt");
//  ifstr >> n >> c >> start;
//  Seg* seg;
//  for (int i = 1; i <= c; i++) {
//      ifstr >> a >> b >> d;
//      if (a == b) {
//          continue;
//      }
//      seg = new Seg(b, d);
//      node[a].addSeg(seg);
//  }
//  ifstr.close();
//}
void shuRu2() {
    Seg* seg;
    cin >> n >> c >> start;
    for (int i = 1; i <= c; i++) {
        cin >> a >> b >> d;
        if (a == b) {
            continue;
        }
        else {
            seg = new Seg(b, d);
            node[a].addSeg(seg);
        }
    }
}
void bianli(int n) {
    inQue[n] = 1;
    if (node[n].head == NULL) {
        return;
    }
    Seg* seg = node[n].head;
    if (n == start) {
        do {
            a = seg->length;
            if(bag[seg->to]==MYINF){
                bag[seg->to] = a;
                luJing[seg->to]=n;
            }
            else{
                if(a<bag[seg->to]){
                    bag[seg->to] = a;
                    luJing[seg->to]=n;
                }   
            }

            que.push(make_pair(bag[seg->to], seg->to));
            seg = seg->next;
        } while (seg != NULL);
        return;
    }
    else {
        do {

            a = seg->length;
            if (bag[seg->to] == MYINF) {
                bag[seg->to] = bag[n] + a;
                luJing[seg->to]=n;
            }
            else {
                if (bag[n] + a < bag[seg->to]) {
                    bag[seg->to] = bag[n] + a;
                    luJing[seg->to]=n;
                }
            }
            que.push(make_pair(bag[seg->to], seg->to));
            seg = seg->next;
        } while (seg != NULL);
    }

}
int main() {
    memset(bag, MYINF, sizeof(bag));
    memset(inQue,0,sizeof(inQue));
    shuRu2();
    //  shuRu1();
    ofstream of("out1.txt");
    bianli(start);
    bag[start] = 0;
    while (!que.empty())
    {
        if (!inQue[que.top().second]) {
            bianli(que.top().second);

        }
        que.pop();
    }
    //  a=304;
//  while(luJing[a]!=start){
//      cout<<a<<"<-";
//      a=luJing[a]; 
//  }
//  cout<<start;

    memset(inQue,0,sizeof(inQue));
    bianli(start);
    bag[start] = 0;
    while (!que.empty())
    {
        if (!inQue[que.top().second]) {
            bianli(que.top().second);

        }
        que.pop();
    }

    for (int i = 1; i <= n; i++) {
        if(bag[i]==MYINF){
            bag[i]=2147483647;
        }
        cout << bag[i] << " ";
//      of<<"i:"<<i<<"::"<<bag[i]<<" ";
    }
    return 0;
}

by liuye11 @ 2022-05-28 22:31:31

@liuye11 真的很玄学

    bianli(start);
    bag[start] = 0;
    while (!que.empty())
    {
        if (!inQue[que.top().second]) {
            bianli(que.top().second);

        }
        que.pop();
    }

    memset(inQue,0,sizeof(inQue));
    bianli(start);
    bag[start] = 0;
    while (!que.empty())
    {
        if (!inQue[que.top().second]) {
            bianli(que.top().second);

        }
        que.pop();
    }

    for (int i = 1; i <= n; i++) {
        if(bag[i]==MYINF){
            bag[i]=2147483647;
        }
        cout << bag[i] << " ";
//      of<<"i:"<<i<<"::"<<bag[i]<<" ";
    }

by liuye11 @ 2022-05-30 17:14:06

自己回答自己的问题，以上出错是因为Dijkstra算法要在满足长度相等的时候符合先进先出的原则，也就是两节点长度相等时应先遍历先入队的节点，而我使用pair排序会对长度和节点序号进行排序，不满足此原则，因此出错，附AC代码

#include<bits/stdc++.h>
#define maxn 500005
#define MYINF -1
using namespace std;
class Node1{
    public:
        int length,to;
        Node1(){

        }
        Node1(int length1,int to1){
            length=length1;
            to=to1;
        }
        bool operator>(const Node1 &nod)const{
            return length>nod.length;
        }
        void set(int length1,int to1){
            length=length1;
            to=to1;
        }
};
class Seg {
public:
    int length, to;
    Seg* next;
    Seg(int to1, int length1) {
        next = NULL;
        length = length1;
        to = to1;
    }
};
class Node {
public:
    //  int count;
    Seg* head;
    Seg* tail;
    Node() {
        head = NULL;
        tail = NULL;
    }
    void addSeg(Seg* seg) {
        if (head == NULL) {
            head = seg;
            tail = seg;
        }
        else {
            tail->next = seg;
            tail = seg;
        }
    }
};
int bag[maxn];
bool inQue[maxn];
Node node[maxn];
//int luJing[maxn]; 
int n, a, b, c, d;
int start, target;
priority_queue<Node1,vector<Node1>,greater<Node1> > que;

void shuRu1() {
    ifstream ifstr("map2.txt");
    ifstr >> n >> c >> start;
    Seg* seg;
    for (int i = 1; i <= c; i++) {
        ifstr >> a >> b >> d;
        if (a == b) {
            continue;
        }
        seg = new Seg(b, d);
        node[a].addSeg(seg);
    }
    ifstr.close();
}
void shuRu2() {
    Seg* seg;
    cin >> n >> c >> start;
    for (int i = 1; i <= c; i++) {
        cin >> a >> b >> d;
        if (a == b) {
            continue;
        }
        else {
            seg = new Seg(b, d);
            node[a].addSeg(seg);
        }
    }
}
void bianli(int n) {
    inQue[n] = 1;
    int to,sdis;
    bool refresh=0;
    Node1 nod;
    if (node[n].head == NULL) {
        return;
    }
    Seg* seg = node[n].head;
    do {
        a = seg->length;
        if (bag[seg->to] == MYINF) {
            bag[seg->to] = bag[n] + a;
            refresh=1;
//          luJing[seg->to]=n;
        }
        else {
            if (bag[n] + a < bag[seg->to]) {
                bag[seg->to] = bag[n] + a;
                refresh=1;
//              luJing[seg->to]=n;
            }
        }
        if(refresh){
            to=seg->to;
            sdis=bag[seg->to];
            nod.set(sdis,to);
            que.push(nod);
//          que.push(make_pair(bag[seg->to], seg->to)); 错误的，pair<int,int>会对两个参数进行排序，不满足第一个参数相等的情况下先进先出的原则 
        }

        seg = seg->next;
    } while (seg != NULL);
}
int main() {
    memset(bag, MYINF, sizeof(bag));
    memset(inQue,0,sizeof(inQue));
    shuRu2();
//      shuRu1();
    ofstream of("out1.txt");
    bag[start] = 0;
    Node1 nod(0,start);
    que.push(nod);
    while (!que.empty())
    {
        if (!inQue[que.top().to]) {
            bianli(que.top().to);
        } 
        que.pop();
    }
    for (int i = 1; i <= n; i++) {
        if(bag[i]==MYINF){
            bag[i]=2147483647;
        }
        cout << bag[i] << " ";
//      of<<bag[i]<<" ";
    }
//  while(luJing[a]!=start){
//      cout<<a<<"<-";
//      a=luJing[a]; 
//  }
//  cout<<start;

    return 0;
}