C++11(clang++ 3.9) 解法, 执行用时: 139ms, 内存消耗: 2404K, 提交时间: 2020-04-10 12:29:11

#include<bits/stdc++.h>
using namespace std;
const int M = 2e5+10;
const int INF=999999;
int n,m,s,t,tot;
int dis[M];
int u[M],v[M],w[M];
int dijkstra(int s,int t){
	for(int i=0;i<=n;i++)
	dis[i]=INF;
	dis[s]=0;
	bool f;
	for(int i=0;i<n;i++){
		f=1;
		for(int j=0;j<tot;j++){
			if(dis[v[j]]!=INF&&dis[u[j]]>dis[v[j]]+w[j])
			dis[u[j]] = dis[v[j]]+w[j],f=0;
		}
		if(f) break;
	}
	if(dis[t]!=INF) return dis[t];
	return 0;
}
int main(){
	cin>>n>>m>>s>>t;
	tot=0;
	int p,x,y,z;
	for(int i=0;i<m;i++){
		cin>>p>>x>>y>>z;
		if(p){
			u[tot]=x,v[tot]=y,w[tot]=z;
			tot++;
			u[tot]=y,v[tot]=x,w[tot]=z;
			tot++;
		}
	}
	if(!dijkstra(s,t))
	cout<<"My gold!!!"<<endl;
	else
	cout<<dijkstra(s,t)<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 188ms, 内存消耗: 7832K, 提交时间: 2020-04-11 15:47:04

#include<bits/stdc++.h>
using namespace std;
const int maxn=999999;
int dis[maxn];
int u[maxn],v[maxn],w[maxn];
int main()
{
    int n,m,s,t;
    int a,b,c,d;
    int l=1;
    cin>>n>>m>>s>>t;
    for (int i=1;i<=m;i++){
        cin>>d>>a>>b>>c;
        if(d)
        {
            u[l]=a,v[l]=b,w[l]=c;
            l++;
            u[l]=b,v[l]=a,w[l]=c;
            l++;
        }
    }
    memset(dis,maxn,sizeof(dis));
    dis[s]=0;
    while (m--)
    {
    	int f=1;
        for (int i=1;i<l;i++){
            if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i],f=0;
        }
        if(f) break;
    }
    if (dis[t]==maxn)cout <<"My gold!!!";
    else cout<<dis[t];
    return 0;
}