比赛 20161215 评测结果 AAAAAAAAAA
题目名称 牛的路线2 最终得分 100
用户昵称 Ostmbh 运行时间 0.059 s
代码语言 C++ 内存使用 1.10 MiB
提交时间 2016-12-16 21:01:27
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=20000;
struct Edge{
	int t,v,id,next;
	Edge(int x,int y,int z):t(x),v(y),id(z){};
};
vector<Edge>A[maxn];
vector<Edge>D[maxn];
int c[maxn];
int f[maxn];
int f2[maxn];
int g[maxn];
bool ok[maxn]={0};
inline void addedge(int x,int y,int z,int k){
	A[x].push_back(Edge(y,z,k));
}
int main(){
	freopen("cowrouteb.in","r",stdin);
	freopen("cowrouteb.out","w",stdout);
	int N;
	int s,t;
	scanf("%d %d %d",&s,&t,&N);
	int a,b;
	for(int i=1;i<=N;i++){
		scanf("%d %d",&a,&b);
		int place=b;
		int ok=0;
		int place2=0;
		int ok2=0;
		for(int j=1;j<=b;j++){
			scanf("%d",&c[j]);
			if(c[j]==s){
				ok=1;
				place=j;
			}
			if(c[j]==t){
				ok2=1;
				place2=j;
			}
		}
		for(int j=place+1;j<=b;j++)
			addedge(s,c[j],a,i);
		for(int j=1;j<place2;j++)
			D[t].push_back(Edge(c[j],a,i));
	}
	memset(f,127/2,sizeof(f));
	f[s]=0;
	for(int i=0;i<A[s].size();i++){
		Edge u=A[s][i];
		if(f[s]+u.v<f[u.t]){
			f[u.t]=f[s]+u.v;
			g[u.t]=u.id;
			continue;
		}
		if(f[s]+u.v==f[u.t]){
			ok[u.t]=1;
		}
	}
	for(int i=1;i<=10000;i++)
		f2[i]=f[i];
	for(int i=0;i<D[t].size();i++){
		Edge u=D[t][i];
		if(f[u.t]+u.v<f2[t]){
			if(g[u.t]!=u.id||ok[u.t])
				f2[t]=f[u.t]+u.v;
		}
	}
	printf("%d\n",f2[t]!=f[0]?f2[t]:-1);
return 0;
}