[USACO 2011 Jan G]Roads and Planes

* Line 1: Four space separated integers: T, R, P, and S
* Lines 2..R+1: Three space separated integers describing a road: $A_i$ , $B_i$ and $C_i$
* Lines R+2..R+P+1: Three space separated integers describing a plane: $A_i$ , $B_i$ and $C_i$

C++14(g++5.4) 解法, 执行用时: 457ms, 内存消耗: 5196K, 提交时间: 2020-05-14 10:52:03

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<unordered_map>
#include<queue>
#include<map>
#include<sstream>
#include<set>
#include<cstdlib>
#include<ctime>
#include<deque>
using namespace std;
const int maxn = 25000 + 50;
typedef unsigned long long ull;
typedef  long long ll;
const int MAX_INF = 0x3f3f3f3f;
struct node
{
	int v;
	int val;
};
vector<node> a[maxn];
int n, r, p, s;
int d[maxn];
bool flag[maxn];
void spfa()
{
	deque<int> p;
	p.push_back(s);
	memset(flag, true, sizeof(flag));
	d[s] = 0;
	while (!p.empty())
	{
		int temp = p.front();
		p.pop_front();
		flag[temp] = true;
		for (int i = 0; i < a[temp].size(); i++)
		{
			int v = a[temp][i].v;
			int val = a[temp][i].val;
			if (d[v] > d[temp] + val)
			{
				d[v] = d[temp] + val;
				if (flag[v])
				{
					flag[v] = false;
					if (!p.empty()&&d[v] <d[p.front()])
						p.push_front(v);
					else
						p.push_back(v);
				}
			}
		}
	}
}
int main()
{
	//记得return 0
	cin >> n >> r >> p >> s;
	for (int i = 0; i < r+p; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		a[u].push_back({ v,w });
		if(i<r)
		a[v].push_back({ u,w });
	}
	memset(d,MAX_INF, sizeof(d));
	spfa();
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == MAX_INF)
			puts("NO PATH");
		else
			printf("%d\n", d[i]);
	}
	return 0;
}

C++ 解法, 执行用时: 540ms, 内存消耗: 6392K, 提交时间: 2022-01-13 10:59:27

#include<bits/stdc++.h>
using namespace std;
struct Edge{int to,nxt,w;}e[500001];
int a,b,c,h[500001],R,P,S,idx,ds[500001],n,iq[500001];
void ad(int a,int b,int c){e[idx].to=b;e[idx].w=c;e[idx].nxt=h[a];h[a]=idx++;}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n>>R>>P>>S;
    for(int i=1;i<=R;i++)cin>>a>>b>>c,ad(a,b,c),ad(b,a,c);
    for(int i=1;i<=P;i++)cin>>a>>b>>c,ad(a,b,c);
    deque<int> q;
    memset(ds,0x3f3f3f3f,sizeof(ds));
    ds[S]=0;
	q.push_back(S);
    while(!q.empty()){
        int u=q.front();
		q.pop_front();
		iq[u]=0;
        for(int i=h[u];~i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w;
            if(ds[v]>ds[u]+w){
                ds[v]=ds[u]+w;
                if(!iq[v]){iq[v]=1;if(q.size()&&ds[v]<ds[q.front()])q.push_front(v);else q.push_back(v);}
            }
        }
    }
    for(int i=1;i<=n;i++){if(ds[i]==0x3f3f3f3f)cout<<"NO PATH\n";else cout<<ds[i]<<"\n";}
    return 0;
}

详情