Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll unsigned long long
- template<typename T>
- inline void read(T&x){
- T k=1;char gc;x=0;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c))x=x*10+c-'0',gc;x*=k;
- }
- const int p1=1e9+7;
- const int p2=998244353;
- const int N=200005;
- const int INF=0x3f3f3f3f;
- int n,m;
- struct Info{
- ll v1,v2,v3;
- Info(){}
- Info(int x){
- v1=v2=v3=x;
- }
- inline void operator += (const Info &a){
- if((v1+=a.v1)>=p1)v1-=p1;
- if((v2+=a.v2)>=p2)v2-=p2;
- v3+=a.v3;
- }
- };
- namespace G1{
- int ecnt;
- int fir[N],nex[N],to[N],dis[N],w[N];
- Info ans[N];
- inline void addedge(int u,int v,int c){
- nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
- }
- priority_queue<pair<int,int> >Q;
- inline void dijkstra(int S){
- memset(dis+1,INF,n<<2);
- ans[S]=1;
- dis[S]=0;
- Q.push(make_pair(0,S));
- while(!Q.empty()){
- int x=Q.top().second;
- int d=-Q.top().first;
- Q.pop();
- if(d!=dis[x])continue;
- for(int i=fir[x];i;i=nex[i]){
- int v=to[i];
- if(dis[v]==dis[x]+w[i]){
- ans[v]+=ans[x];
- }
- if(dis[v]>dis[x]+w[i]){
- ans[v]=ans[x];
- dis[v]=dis[x]+w[i];
- Q.push(make_pair(-dis[v],v));
- }
- }
- }
- }
- inline void work(){
- dijkstra(1);
- if(dis[n]==INF)puts("-1"),exit(0);
- }
- }
- namespace G2{
- int ecnt;
- int fir[N],nex[N],to[N],dis[N],w[N];
- Info ans[N];
- inline void addedge(int u,int v,int c){
- nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
- }
- priority_queue<pair<int,int> >Q;
- inline void dijkstra(int S){
- memset(dis+1,INF,n<<2);
- ans[S]=1;
- dis[S]=0;
- Q.push(make_pair(0,S));
- while(!Q.empty()){
- int x=Q.top().second;
- int d=-Q.top().first;
- Q.pop();
- if(d!=dis[x])continue;
- for(int i=fir[x];i;i=nex[i]){
- int v=to[i];
- if(dis[v]==dis[x]+w[i]){
- ans[v]+=ans[x];
- }
- if(dis[v]>dis[x]+w[i]){
- ans[v]=ans[x];
- dis[v]=dis[x]+w[i];
- Q.push(make_pair(-dis[v],v));
- }
- }
- }
- }
- inline void work(){
- dijkstra(n);
- }
- }
- inline bool check(const Info &a,const Info &b,const Info &c){
- if(a.v1*b.v1%p1!=c.v1)return 0;
- if(a.v2*b.v2%p2!=c.v2)return 0;
- if(a.v3*b.v3!=c.v3)return 0;
- return 1;
- }
- int main(){
- freopen("c.in","r",stdin);
- freopen("c.out","w",stdout);
- r(n),r(m);
- for(int i=1;i<=m;++i){
- int u,v,c;
- r(u),r(v),r(c);
- G1::addedge(u,v,c);
- G2::addedge(v,u,c);
- }
- G1::work();
- G2::work();
- int ans=0;
- for(int i=1;i<=n;++i){
- if(G1::dis[i]+G2::dis[i]==G1::dis[n]&&check(G1::ans[i],G2::ans[i],G1::ans[n])){
- ans++;
- }
- }
- printf("%d\n",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement