1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| namespace Spfa{
#define pp pair<int,int>
#define f first
#define s second
inline int read(){
register int a=0,f=1;register char c;
while((c=getchar())<'0')if(c=='-')f=-1;;
while(c>='0')a=a*10+(c^48),c=getchar();
return a*f;
}
const int MAXN = 1e5+5;
const int MAXM = 2e5+5;
int n,m,k,dist[MAXN],head[MAXN],tot,sz[MAXN];
bool vis[MAXN];
struct Edge{
int f,t,nxt,dis;
}edge[MAXM];
inline void add(int f,int t, int d){
edge[++tot].f = f;
edge[tot].t = t;
edge[tot].dis = d;
edge[tot].nxt = head[f];
head[f] = tot;
}
inline bool spfa(int source){
queue<int> q;
memset(dist,0x3f3f,sizeof(dist));
dist[source] = 0;
q.push(source);
while(!q.empty()){
int qf = q.front();q.pop();
vis[qf] = false;
for (int i=head[qf];i;i=edge[i].nxt){
int v = edge[i].t,d = edge[i].dis;
if (dist[v]>dist[qs]+d){
dist[v] = dist[qs]+d;
if (++sz[v]>n) return true;
if (!vis[v]) vis[v] = true,q.push(v);
}
}
}
return false;
}
void init();
void solve();
}
|
