B. Failing Components
题意就是单向图，从起点开始找最短路，然后统计一下个数就可以。方向是从b到a，权值为s。
直接最短路跑迪杰斯特拉，一开始用数组版的没过，换了一个队列版的过了。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<queue> 7 #include<cstring> 8 #include<algorithm> 9 using namespace std; 10 typedef long long ll; 11 const int maxn=1e5+10; 12 const double eps=1e-7; 13 const int N=1e5+10; 14 const int INF=0x3f3f3f3f; 15 int head[N*2], nex[N*2], to[N*2], val[N*2], dis[N], vis[N], tot; 16 struct cmp{ 17 bool operator()(int a,int b) { 18 return dis[a]>dis[b]; 19 } 20 }; 21 priority_queue<int, vector<int>, cmp > Q; 22 void init() { 23 tot = 0; 24 while(!Q.empty()) Q.pop(); 25 memset(head, -1, sizeof(head)); 26 memset(dis, INF, sizeof(dis)); 27 memset(vis, 0, sizeof(vis)); 28 } 29 void addedge(int u, int v, int w) { 30 to[tot] = v; 31 nex[tot] = head[u]; 32 val[tot] = w; 33 head[u] = tot++; 34 } 35 void Dijkstra(int S) { 36 Q.push(S); 37 dis[S] = 0; 38 while(!Q.empty()) { 39 int u = Q.top(); 40 Q.pop(); 41 for(int i=head[u]; i!=-1; i=nex[i]) { 42 int v = to[i]; 43 if(!vis[v] && dis[u]+val[i] < dis[v]) { 44 dis[v] = dis[u]+val[i]; 45 Q.push(v); 46 } 47 } 48 } 49 } 50 int main(){ 51 int t; 52 scanf("%d",&t); 53 while(t--){ 54 init(); 55 int n,p,k; 56 scanf("%d%d%d",&n,&p,&k); 57 int h,l,val; 58 for(int i=0;i<p;i++){ 59 scanf("%d%d%d",&h,&l,&val); 60 addedge(l,h,val); 61 } 62 Dijkstra(k); 63 int num=0; 64 int maxx=-1; 65 for(int i=1;i<=n;i++){ 66 if(dis[i]!=INF){ 67 num++; 68 maxx=max(maxx,dis[i]); 69 } 70 } 71 cout<<num<<" "<<maxx; 72 cout<<endl; 73 } 74 return 0; 75 }