STABLE - VOI10 - Ổn định
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<queue>
#include<vector>
#define MAX 11111
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
const int INF=1e7;
bool a[MAX][MAX];
vi g[MAX];
int n,m,s,r;
int d[MAX];
int c[MAX];
void loadgraph(void)
{
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&s);
int i,u,v;
for (i=1;i<=n;i=i+1)
{
d[i]=INF;
c[i]=0;
}
for (i=1;i<=m;i=i+1)
{
scanf("%d",&u);
scanf("%d",&v);
if (a[u][v]) continue;
g[u].push_back(v);
a[u][v]=true;
}
c[s]=1;
d[s]=0;
}
void dijkstra(void)
{
priority_queue<ii,vector<ii>,greater<ii> > q;
q.push(ii(0,s));
while (!q.empty())
{
ii x=q.top();
q.pop();
int i;
int w=x.first;
int u=x.second;
for (i=0;i<g[u].size();i=i+1)
{
if (d[u]+1==d[g[u][i]]) {
c[g[u][i]]+=c[u];
if (c[g[u][i]]>17) c[g[u][i]]=17;
}
else
if (d[u]+1<d[g[u][i]])
{
d[g[u][i]]=d[u]+1;
c[g[u][i]]=c[u];
if (c[g[u][i]]>17) c[g[u][i]]=17;
q.push(ii(d[u]+1,g[u][i]));
}
}
}
int cnt=0;
int i;
for (i=1;i<=n;i=i+1)
if (c[i]>1) cnt++;
printf("%d",cnt);
}
int main(void)
{
loadgraph();
dijkstra();
}