C++14(g++5.4) 解法, 执行用时: 65ms, 内存消耗: 11756K, 提交时间: 2020-04-21 20:22:17

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10,M=2e6+10;
int n,m,s,t,d[N],a[N],vis[N];
int head[N],nex[M],to[M],w[M],tot;
inline void add(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
void Dijkstra(){
	priority_queue<pair<int,int> > q; q.push({0,s}); memset(d,0x3f,sizeof d); d[s]=0;
	while(q.size()){
		int u=q.top().second;	q.pop();
		if(vis[u])	continue;	vis[u]=0;
		for(int i=head[u];i;i=nex[i])	if(d[to[i]]>d[u]+w[i]){
			d[to[i]]=d[u]+w[i];	q.push({-d[to[i]],to[i]});
		}
	}
}
signed main(){
	cin>>n>>m>>s>>t;
	for(int i=1,x,y,z;i<=m;i++){
		cin>>x>>y>>z;
		for(int j=1;j<=z;j++)	scanf("%d",&a[j]),add(a[j],a[j]+i*n,x),add(a[j]+i*n,a[j],0);
		for(int j=1;j<z;j++)	add(i*n+a[j],i*n+a[j+1],y),add(i*n+a[j+1],i*n+a[j],y);
	}
	Dijkstra();	if(d[t]>=0x3f3f3f3f)	d[t]=-1;
	cout<<d[t];
	return 0;
}

C++ 解法, 执行用时: 138ms, 内存消耗: 4404K, 提交时间: 2022-05-26 08:33:17

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e3 + 10;
int n, m, s, t;
int c[N], e[N][N], dis[N];
bool vis[N];
int main(){
	memset(dis, 0x3f, sizeof dis);
	memset(e, 0x3f, sizeof e);
	cin >> n >> m >> s >> t;
	for (int i = 0, x, y, z; i < m; ++i){
		cin >> x >> y >> z;
		for (int j = 0; j < z; ++j){
			cin >> c[j];
			for (int k = j - 1; k >= 0; k--)
				e[c[k]][c[j]] = e[c[j]][c[k]] = min(e[c[j]][c[k]], x + (j - k) * y);
		}
	}
	dis[s] = 0;
	for (int i = 0, u = -1; i < n; ++i, u = -1){
		for (int j = 1; j <= n; ++j)
			if (!vis[j] && (u == -1 || dis[j] < dis[u])) u = j;
		vis[u] = 1;
		for (int j = 1; j <= n; ++j) dis[j] = min(dis[j], dis[u] + e[u][j]);
	}
	if (dis[t] == 0x3f3f3f3f) cout << -1;
	else cout << dis[t];
	return 0;
}