# sgu-240 Runaway

#### AC代码：

``````#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

int N,M,H,S,EN;
struct bian_
{
int aim;
int next;
int T;
int R;
int P;
}bian[20010]={{0,0,0,0,0}};

int First[110]={0};

int ans=2e9;
int ansp=0;
int fa[110]={0};
int Out[110]={0};
int dist[110]={0};
int dui[810]={0};
int duip=0;
int hash[110]={0};
int E[110]={0};

void Add(int a,int b,int t,int r,int p,int k)
{
bian[k].next=First[a];
bian[k].aim=b;
bian[k].T=t;
bian[k].R=r;
bian[k].P=p;
First[a]=k;
return;
}

bool check(int Max)
{
memset(dist,-1,sizeof(dist));
duip=0;
dist[S]=0;
dui[++duip]=S;
for(int i=1;i<=duip;i++)
{
int u=dui[i];
for(int p=First[u];p!=0;p=bian[p].next)
{
int TT=dist[u]+bian[p].T;
int v=bian[p].aim;
if(dist[v]==-1) dist[v]=2147483647;
if((long long)TT*bian[p].P+bian[p].R<=(long long)Max && TT<dist[v])
{
fa[v]=u;
dist[v]=TT;
if(hash[v]==0)
{
hash[v]=1;
dui[++duip]=v;
}
}
}
hash[u]=0;
}
for(int i=1;i<=EN;i++)
{
if(dist[E[i]]!=2147483647 && dist[E[i]]!=-1)
{
ansp=0;
for(int j=E[i];j!=S;j=fa[j])
Out[++ansp]=j;
return true;
}
}
return false;
}

int main()
{
freopen("sgu240.in","r",stdin);
freopen("sgu240.out","w",stdout);
scanf("%d%d%d%d%d",&N,&M,&H,&S,&EN);
for(int i=1;i<=M;i++)
{
int a,b,t,r,p;
scanf("%d%d%d%d%d",&a,&b,&t,&r,&p);
}
for(int i=1;i<=EN;i++)
scanf("%d",&E[i]);
for(int L=0,R=H;L<=R;)
{
int mid=(L+R)>>1;
if(check(mid)==true)
{
ans=mid;
R=mid-1;
}
else L=mid+1;
}
if(ans==2e9)
cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl;
cout<<ans<<endl;
cout<<ansp+1<<‘ ‘<<S;
for(int i=ansp;i>=1;i--)
printf(" %d",Out[i]);
cout<<endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}``````

## 【SGU 390】Tickets （数位DP）

Tickets Description Conductor is quite a boring profession, as all you have to do is just to sell tickets to the passengers. So no wonder that once upon a time in a faraway galaxy one conductor decided to diversify this occupation. Now this conductor

## ACM: SGU 101 Domino- 欧拉回路-并查集

sgu 101 - Domino Time Limit:250MS     Memory Limit:4096KB     64bit IO Format:%I64d & %I64u Description Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The bl

## SGU 乱搞日志

SGU 100 A+B :太神不会 SGU 101 Domino: 题目大意:有N张骨牌,两张骨牌有两面有0到6的数字,能相连当且仅当前后数字相同,问能否有将N张骨牌连接的方案?思路:裸的欧拉回路,注意自环,连通 1 //sgu101 2 #include<iostream> 3 #include<cstdio> 4 #include <math.h> 5 #include<algorithm> 6 #include<string.h> 7 #i

## SGU 193.Chinese Girls&#39; Amusement

/* 实际上就是求一个k,满足k<=n/2,且gcd(n,k)=1 如果n为奇数,k为[n/2] 如果n为偶数,k=n/2-1-(n/2)%2 */ #include <iostream> using namespace std; string s; void div2() { string t; int l = s.size() - 1, tem = s[0] - '0'; if (tem > 1) t += '0' + tem / 2; tem &= 1; for (i

## SGU 112 a^b-b^a

JAVA大数.... a^b-b^a Time Limit: 250MS   Memory Limit: 4096KB   64bit IO Format: %I64d & %I64u [Submit]   [Go Back]   [Status] Description You are given natural numbers a and b. Find ab-ba. Input Input contains numbers a and b (1≤a,b≤100). Output Write