WA on 3,5
by The_long_way__ @ 2024-01-23 15:32:56
????
by 13644480207jnh @ 2024-01-23 16:03:11
重写了,还是60分
by The_long_way__ @ 2024-01-24 15:14:44
```cpp
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int to,dist,next;
}E[30001];
int A[101];
int head[101],k=1,D[101],N,M;
void addedge(int u,int v,int dist){
E[k]={v,dist,head[u]};
D[v]++;
head[u]=k++;
}
void topsort(){
stack<int> S;
for(int i=1;i<=N;i++){
if(D[i]==0){
S.push(i);
}
}
while(!S.empty()){
int v=S.top();
S.pop();
if(A[v]>0){
for(int it=head[v];it!=-1;it=E[it].next){
A[E[it].to]+=E[it].dist*A[v];
if(!(--D[E[it].to])){
S.push(E[it].to);
}
}
}
}
}
int main(){
memset(head,-1,sizeof(head));
cin>>N>>M;
for(int i=1;i<=N;i++){
int u;
cin>>A[i]>>u;
A[i]-=u;
}
for(int i=1;i<=M;i++){
int u,v,dist;
cin>>u>>v>>dist;
addedge(u,v,dist);
}
int cnt=0,out[101];
for(int i=1;i<=N;i++){
if(head[i]==-1)out[++cnt]=i;
}
topsort();
int cnt2=0;
for(int i=1;i<=cnt;i++){
if(A[out[i]]>0){
cout<<out[i]<<' '<<A[out[i]]<<endl;
cnt2++;
}
}
if(cnt2==0)cout<<"NULL"<<endl;
return 0;
}
```
by The_long_way__ @ 2024-01-24 15:15:06