比赛 |
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;
}