C++(g++ 7.5.0) 解法, 执行用时: 150ms, 内存消耗: 10512K, 提交时间: 2023-05-20 23:58:07

#include <bits/stdc++.h>

using i64 = std::int64_t;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m;
	std::cin >> n >> m;

	std::vector<int> a(m), b(m);
	std::vector<std::vector<std::pair<int, int>>> adj(n);

	for (int i = 0; i < m; i++) {
		int x, y;
		std::cin >> x >> y >> a[i] >> b[i];
		x--, y--;
		adj[x].emplace_back(y, i);
		adj[y].emplace_back(x, i);
	}

	int s, t;
	std::cin >> s >> t;
	s--, t--;

	std::vector<i64> dist(n, -1), ndist(n, -1);
	std::priority_queue<std::pair<i64, int>> q;
	q.emplace(0, s);

	while (!q.empty()) {
		auto [d, x] = q.top();
		q.pop();
		if (dist[x] != -1) continue;
		dist[x] = -d;
		for (auto [y, id] : adj[x]) {
			if (dist[y] == -1) {
				q.emplace(d - a[id], y);
			}
		}
	}

	q.emplace(0, t);
		while (!q.empty()) {
		auto [d, x] = q.top();
		q.pop();
		if (ndist[x] != -1) continue;
		ndist[x] = -d;
		for (auto [y, id] : adj[x]) {
			if (ndist[y] == -1) {
				q.emplace(d - b[id], y);
			}
		}
	}

	std::vector<i64> ans(n, ~0uLL >> 1);
	for (int i = n - 1; i >= 0; i--) {
		if (i < n - 1) {
			ans[i] = std::min(ans[i], ans[i + 1]);
		}
		ans[i] = std::min(ans[i], dist[i] + ndist[i]);
	}

	for (auto x : ans) {
		std::cout << x << "\n";
	}

	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 195ms, 内存消耗: 10852K, 提交时间: 2019-09-04 10:24:37

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+1;
const ll inf=(1LL<<50);
int cnt=0,s,t,n,m,w1[maxn<<1],w2[maxn<<1],head[maxn],to[maxn<<1],nt[maxn<<1];
ll d1[maxn],d2[maxn],sum[maxn];
bool vis[maxn];
void add(int a,int b,int x,int y)
{
	++cnt;nt[cnt]=head[a];head[a]=cnt;to[cnt]=b;w1[cnt]=x;w2[cnt]=y;
}
void spfa(int s,int *w,ll *d)
{
	memset(vis,false,sizeof(vis));
	fill(d,d+maxn,inf);
	queue<int>q;
	q.push(s);
	d[s]=0;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=false;
		for(int i=head[t];i!=-1;i=nt[i])
		{
			int u=to[i];
			if(d[t]+w[i]<d[u]) 
			{
					d[u]=d[t]+w[i];
				if(!vis[u]) vis[u]=true,q.push(u);
			}
		}
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	fill(head,head+maxn,-1);
	while(m--)
	{
		int t1,t2,t3,t4;
		scanf("%d %d %d %d",&t1,&t2,&t3,&t4);
		add(t1,t2,t3,t4);
		add(t2,t1,t3,t4);
	}
	scanf("%d %d",&s,&t);
	spfa(s,w1,d1);
	spfa(t,w2,d2);
	sum[n]=d1[n]+d2[n];
	for(int i=n-1;i>=1;--i) sum[i]=min(sum[i+1],d1[i]+d2[i]); 
	for(int i=1;i<=n;++i) printf("%lld\n",sum[i]);
}

C++14(g++5.4) 解法, 执行用时: 218ms, 内存消耗: 11360K, 提交时间: 2020-03-10 15:26:10

#include<bits/stdc++.h>
using namespace std;

typedef  long long ll;
const int maxn=1e5+10;
const ll inf=1ll<<50;

ll s,t,n,m,cnt,S,T;
ll head[maxn],dis1[maxn],dis2[maxn],ans[maxn];
queue<int> que;

struct node{
	ll v,w1,w2,nex;
}e[maxn<<1];
bool vis[maxn];

void add( ll u,ll v,ll w1,ll w2 )
{
	e[++cnt]={v,w1,w2,head[u]};
	head[u]=cnt;
}


void spfa( ll s,ll *dis,int num )
{
	for( int i=1;i<=n;i++ ) dis[i]=inf;
	memset(vis,0,sizeof(vis));
	que.push(s);
	dis[s]=0;
	while( !que.empty() )
	{
		ll u=que.front();que.pop();
		vis[u]=0;
		for( ll i=head[u];i;i=e[i].nex )
		{
			ll v=e[i].v,w= ( num ? e[i].w2 : e[i].w1 );
			if( dis[v]>dis[u]+w )
			{
				dis[v]=dis[u]+w;
				if( !vis[v] )vis[v]=1,que.push(v);
			}
		}	
		
	} 
}

int main()
{
	cin>>n>>m;
	for( int i=1;i<=m;i++ )
	{
		int u,v,w1,w2;cin>>u>>v>>w1>>w2;
		add(u,v,w1,w2);add(v,u,w1,w2);
	}
	cin>>S>>T;
	spfa(S,dis1,0);
	spfa(T,dis2,1);
	ans[n]=dis1[n]+dis2[n];
	for( int i=n-1;i>=1;i-- ) ans[i]=min(ans[i+1],dis1[i]+dis2[i]);
	for( int i=1;i<=n;i++ ) cout<<ans[i]<<"\n";
}