萌新求助
查看原帖
萌新求助
114914
一只书虫仔楼主2020/7/11 10:40

10 / 30 分,主要就是程序中标的 for 循环出错了
萌新求助 /kel/dk 求大佬帮忙

#include <bits/stdc++.h>

using namespace std;

struct node {
	int val, next, length;
} e1[50086], e2[50086], e3[50086];

int n, m, cnt, pnt, hnt;
int dist1[50086], sum1[50086], head1[50086];
int dist2[50086], sum2[50086], head2[50086];
int dist3[50086], sum3[50086], head3[50086];
const int inf = 0x3f3f3f3f;

void AddEdge01 (int u, int v, int w) {
	e1[cnt].val = v;
	e1[cnt].next = head1[u];
	e1[cnt].length = w;
	head1[u] = cnt;
	cnt--;
}

void AddEdge02 (int u, int v, int w) {
	e2[pnt].val = v;
	e2[pnt].next = head2[u];
	e2[pnt].length = w;
	head2[u] = pnt;
	pnt--;
}

struct cmp01 {
    bool operator () (int a, int b) {
        return dist1[a] > dist1[b];
    }
};

struct cmp02 {
	bool operator () (int a, int b) {
		return dist2[a] > dist2[b];
	}
}; 

void SPFA01 () {
	int s = n;
	priority_queue <int, vector<int>, cmp01> q1;
	for (int i = 1; i <= n; i++)
		dist1[i] = inf;
	dist1[s] = 0;
	sum1[s] = 1;
	q1.push(s);
	while (!q1.empty()) {
		int cur = q1.top();
		q1.pop();
		sum1[cur] = 0;
		for (int p = head1[cur]; p > 0; p = e1[p].next)
			if (dist1[e1[p].val] > dist1[cur] + e1[p].length) {
				dist1[e1[p].val] = dist1[cur] + e1[p].length;
				if (!sum1[e1[p].val]) {
					q1.push(e1[p].val);
					sum1[e1[p].val] = 1;
				}
			}
	}
}

void SPFA02 () {
	int s = n;
	priority_queue <int, vector<int>, cmp02> q2;
	for (int i = 1; i <= n; i++)
		dist2[i] = inf;
	dist2[s] = 0;
	sum2[s] = 1;
	q2.push(s);
	while (!q2.empty()) {
		int cur = q2.top();
		q2.pop();
		sum2[cur] = 0;
		for (int p = head2[cur]; p > 0; p = e2[p].next)
			if (dist2[e2[p].val] > dist2[cur] + e2[p].length) {
				dist2[e2[p].val] = dist2[cur] + e2[p].length;
				if (!sum2[e2[p].val]) {
					q2.push(e2[p].val);
					sum2[e2[p].val] = 1;
				}
			}
	}
}

void AddEdge03 (int u, int v, int w) {
	e3[++hnt].val = v;
	e3[hnt].next = head3[u];
	e3[hnt].length = w;
	head3[u] = hnt;
}

void SPFA03 () {
	int s = 1;
	priority_queue <int, vector<int>, cmp02> q3;
	for (int i = 1; i <= n; i++)
		dist3[i] = inf;
	dist3[s] = 0;
	sum3[s] = 1;
	q3.push(s);
	while (!q3.empty()) {
		int cur = q3.top();
		q3.pop();
		sum3[cur] = 0;
		for (int p = head3[cur]; p > 0; p = e3[p].next)
			if (dist3[e3[p].val] > dist3[cur] + e3[p].length) {
				dist3[e3[p].val] = dist3[cur] + e3[p].length;
				if (!sum3[e3[p].val]) {
					q3.push(e3[p].val);
					sum3[e3[p].val] = 1;
				}
			}
	}
}

int main () {
	scanf("%d%d", &n, &m);
	cnt = m, pnt = m;
	for (int i = 1, u, v, w1, w2; i <= m; i++) {
		scanf("%d%d%d%d", &u, &v, &w1, &w2);
		AddEdge01(v, u, w1);
		AddEdge02(v, u, w2);
		AddEdge03(u, v, 0);
	}
	SPFA01(), SPFA02();
	// Part 1 complete : Slowest Time - 47 ms
	for (int i = 1; i <= m; i++) { // 这个 for 循环出错 
		if (dist1[e3[i].next] - dist1[e3[i].val] != e3[i].length)
			e3[i].length++;
		if (dist2[e3[i].next] - dist2[e3[i].val] != e3[i].length)
			e3[i].length++;
	}
	SPFA03();
	printf("%d", dist3[n]);
	// Part 2 not complete
	return 0;
}
2020/7/11 10:40
加载中...