pypy3 解法, 执行用时: 176ms, 内存消耗: 25752K, 提交时间: 2023-01-15 22:12:26

n,m,s,t=map(int,input().split())
d=[float("inf")]*(n+1)
d[s]=0
vis=[0]*(n+1)
mp=[]
for _ in range(n+1):
    mp.append([])
for _ in range(m):
    u,v,w=map(int,input().split())
    mp[u].append([v,w])
    mp[v].append([u,w])
flag=0
for i in range(n):
    k=0
    mind=100000000
    for j in range(1,n+1):
        if vis[j]==0 and d[j]<mind:
            mind=d[j]
            k=j
    if k==0:break
    vis[k]=1
    for j in mp[k]:
        d[j[0]]=min(d[j[0]],d[k]+j[1])
     
if d[t]==float("inf"):
    print(-1)
else:print(d[t])

Python3 解法, 执行用时: 208ms, 内存消耗: 6688K, 提交时间: 2022-06-02 19:42:09

n,m,s,t=map(int,input().split())
d=[float("inf")]*(n+1)
d[s]=0
vis=[0]*(n+1)
mp=[]
for _ in range(n+1):
    mp.append([])
for _ in range(m):
    u,v,w=map(int,input().split())
    mp[u].append([v,w])
    mp[v].append([u,w])
flag=0
for i in range(n):
    k=0
    mind=100000000
    for j in range(1,n+1):
        if vis[j]==0 and d[j]<mind:
            mind=d[j]
            k=j
    if k==0:break
    vis[k]=1
    for j in mp[k]:
        d[j[0]]=min(d[j[0]],d[k]+j[1])
    
if d[t]==float("inf"):
    print(-1)
else:print(d[t])

C++(g++ 7.5.0) 解法, 执行用时: 842ms, 内存消耗: 4352K, 提交时间: 2023-05-26 14:48:50

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,g[1005][1005];
const int inf=0x3f3f3f3f;
int main()
{
	memset(g,inf,sizeof(g));
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int a,b,v;
		cin>>a>>b>>v;
		g[a][b]=min(g[a][b],v);
		g[b][a]=g[a][b];
	}
	for(int i=1;i<=n;i++)	g[i][i]=0;
	for(int k=1;k<=n;k++)
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	  	g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
	if(g[s][t]==inf) {
		cout<<-1; return 0;
	}
	cout<<g[s][t];
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 21ms, 内存消耗: 608K, 提交时间: 2023-07-27 20:21:19

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

int main(){
  int n, m, s, t; cin >> n >> m >> s >> t;
  vector<array<int, 3>> G(m);
  for (auto &[a,b,v]: G) cin >> a >> b >> v;
  vector<int> D(n+1, 0x3f3f3f3f);
  D[s] = 0;
  for (int i = 0; i < n; i++) {
    for (auto [a, b, v]: G) D[a] = min(D[a], D[b]+v), D[b] = min(D[b], D[a]+v);
  }
  if (D[t] == 0x3f3f3f3f) D[t] = -1;
  cout << D[t] << endl;
}