比赛 |
20150408 |
评测结果 |
AAAAWWTTTT |
题目名称 |
牛的路线2 |
最终得分 |
40 |
用户昵称 |
Asm.Def |
运行时间 |
4.008 s |
代码语言 |
C++ |
内存使用 |
39.67 MiB |
提交时间 |
2015-04-08 20:47:18 |
显示代码纯文本
/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define getc() getchar()
template<class T>inline void getd(T &x){
char ch = getc();bool neg = false;
while(!isdigit(ch) && ch != '-')ch = getc();
if(ch == '-')ch = getc(), neg = true;
x = ch - '0';
while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 10003, inf = 0x3f3f3f3f;
int Route[501][503], R_cnt[maxn], A, B, N, dis[maxn], Vcnt;
struct ESet{int *begin, w;}E[maxn][501];
bool exi[maxn];
inline void init(){
getd(A), getd(B), getd(N);
int i, j, t, w, cnt;
for(i = 0;i < N;++i){
getd(w), getd(cnt);
for(j = 0;j < cnt;++j){
getd(t);Route[i][j] = t;
if(!exi[t])exi[t] = true, ++Vcnt;
E[t][R_cnt[t]].begin = Route[i] + j;
E[t][R_cnt[t]++].w = w;
}
Route[i][cnt] = -1;
}
memset(dis, 0x3f, sizeof(dis));dis[A] = 0;
}
//Heap
#define L(x) (x << 1)
#define R(x) ((x << 1) + 1)
#define P(x) (x >> 1)
int Heap[maxn], ptr[maxn], size;
inline bool validup(int x){return x == 1 || dis[Heap[P(x)]] <= dis[Heap[x]];}
inline bool validdown(int x){
if(L(x) > size)return true;if(dis[Heap[L(x)]] > dis[Heap[x]])return false;
return R(x) > size || dis[Heap[R(x)]] >= dis[Heap[x]];
}
inline void MtDown(int x){
int tmp, repl;
while(!validdown(x)){
tmp = dis[Heap[x]];
if(L(x) < tmp)repl = L(x), tmp = dis[Heap[L(x)]];
if(R(x) <= size && R(x) < tmp)repl = R(x);
swap(Heap[x], Heap[repl]);
swap(ptr[Heap[x]], ptr[Heap[repl]]);
x = repl;
}
}
inline void MtUp(int x){
while(!validup(x)){
swap(Heap[x], Heap[P(x)]);
swap(ptr[Heap[x]], ptr[Heap[P(x)]]);
x = P(x);
}
}
bool inheap[maxn], known[maxn];
inline int PopMin(){int ans = Heap[1];swap(Heap[1], Heap[size--]);inheap[ans] = false;ptr[Heap[1]] = 1;MtDown(1);return ans;}
inline void Insert(int x){inheap[x] = true;Heap[++size] = x;ptr[Heap[size]] = size;MtUp(size);}
//Heap
#define LoopAdj(u, it, i) for(i = 0;i < R_cnt[u];++i)for(it = E[u][i].begin + 1;~(*it);++it)
inline void work(){
Insert(A);
int u, i, *it;
LoopAdj(A, it, i)if(E[A][i].w < dis[*it]){
//printf("%d->%d, val=%d\n", A, *it, E[A][i].w);
dis[*it] = E[A][i].w;
if(!inheap[*it])Insert(*it);
else MtUp(ptr[*it]);
}
while(!known[B] && size){
u = PopMin();known[u] = true;
/*for(i = 1;i <= size;++i){
printf("Heap[%d] = %d, dis = %d\n", i, Heap[i], dis[Heap[i]]);
}*/
LoopAdj(u, it, i)if(!known[*it] && dis[*it] > dis[u] + E[u][i].w){
//printf("%d->%d, val=%d\n", u, *it, E[u][i].w);
dis[*it] = dis[u] + E[u][i].w;
if(!inheap[*it])Insert(*it);
else MtUp(ptr[*it]);
}
}
printf("%d\n", dis[B] == inf ? -1 : dis[B]);
}
int main(){
#ifdef DEBUG
freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
SetFile(cowrouteb);
#endif
init();
work();
#ifdef DEBUG
printf("\n%lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}