Submission #3607803
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007
//プラキュー(二分ヒープ)(優先度変更ありバージョン)
ll heapN,heap[1<<20],heapinv[1<<20];
int PQhikaku(int i,int j);//jの方が優先度が高いならtrueを返す
void PQchange(int n);
void heap_utod(int n){
if(2*n>heapN)return;
int rflag=(2*n+1<=heapN)&&(PQhikaku(2*n,2*n+1));
if(PQhikaku(n,2*n+rflag)){
ll temp=heap[2*n+rflag];
heap[2*n+rflag]=heap[n];
heap[n]=temp;
heapinv[heap[n]]=n;
heapinv[heap[2*n+rflag]]=2*n+rflag;
heap_utod(2*n+rflag);
}
}
void heap_dtou(int n){
if(n==1||PQhikaku(n,n/2))return;
ll temp=heap[n];
heap[n]=heap[n/2];
heap[n/2]=temp;
heapinv[heap[n]]=n;
heapinv[heap[n/2]]=n/2;
heap_dtou(n/2);
}
ll PQpop(){
ll rr=heap[1];
heapinv[heap[1]]=0;
heap[1]=heap[heapN--];
heapinv[heap[1]]=1;
heap_utod(1);
return rr;
}
void PQpush(ll n){
heap[++heapN]=n;
heapinv[heap[heapN]]=heapN;
heap_dtou(heapN);
}
//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g,c;}E;
typedef struct graph{
ll vcnt,ecnt;
E e[400010];//適宜変える
ll id[100010];//適宜変える
}G;
int esort(const void*a,const void*b){
E*p=(E*)a,*q=(E*)b;
if((*p).s<(*q).s)return -1;
if((*p).s>(*q).s)return 1;
if((*p).g<(*q).g)return -1;
return 1;
}
G g;
ll s,t;
void readgraph(){
//適宜変える
ll n,m;
scanf("%lld%lld",&n,&m);
scanf("%lld%lld",&s,&t);
s--,t--;
rep(i,0,m){
ll x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
x--,y--;
g.e[2*i].s=x;
g.e[2*i].g=y;
g.e[2*i].c=c;
g.e[2*i+1].s=y;
g.e[2*i+1].g=x;
g.e[2*i+1].c=c;
}
g.vcnt=n;
g.ecnt=2*m;
qsort(g.e,g.ecnt,sizeof(E),esort);
int p=0;
rep(i,0,g.vcnt){
while(p<g.ecnt&&g.e[p].s<i)p++;
g.id[i]=p;
}
g.id[g.vcnt]=g.ecnt;//一応番兵
}
//早い方のダイクストラ
//グラフと始点を引いて各点への最短距離・最短経路を返す
//辺は有向
//プラキューを使う
//O((E+V)logV)
ll daikusutorappp[1<<20];
ll daikusutora222[1<<20];
void daikusutora2(G g,ll s){
rep(i,0,g.vcnt)daikusutorappp[i]=i==s?0:INF;
rep(i,0,g.vcnt)daikusutora222[i]=i==s?1:0;//追加
rep(i,0,g.vcnt)PQpush(i);
while(heapN){
ll mv=PQpop();
for(ll t=g.id[mv];g.e[t].s==mv;t++){
if(daikusutorappp[g.e[t].g]>daikusutorappp[mv]+g.e[t].c){
daikusutorappp[g.e[t].g]=daikusutorappp[mv]+g.e[t].c;
daikusutora222[g.e[t].g]=daikusutora222[mv];//追加
PQchange(g.e[t].g);
}else if(daikusutorappp[g.e[t].g]==daikusutorappp[mv]+g.e[t].c){//追加
daikusutora222[g.e[t].g]+=daikusutora222[mv];//追加
daikusutora222[g.e[t].g]%=MOD;
}
}
}
}
int PQhikaku(int i,int j){return daikusutorappp[heap[i]]>daikusutorappp[heap[j]];}
void PQchange(int n){if(heapinv[n])heap_dtou(heapinv[n]);}
ll scost[100010],scnt[100010];
ll tcost[100010],tcnt[100010];
int main(){
readgraph();
daikusutora2(g,s);
rep(i,0,g.vcnt){
scost[i]=daikusutorappp[i];
scnt[i]=daikusutora222[i];
}
daikusutora2(g,t);
rep(i,0,g.vcnt){
tcost[i]=daikusutorappp[i];
tcnt[i]=daikusutora222[i];
}
ll d=scost[t];
ll ans=scnt[t]*tcnt[s]%MOD;
rep(i,0,g.vcnt)if(scost[i]*2==d)ans=(ans-scnt[i]*tcnt[i]%MOD*tcnt[i]%MOD*scnt[i]%MOD+MOD)%MOD;
rep(i,0,g.ecnt){
if(scost[g.e[i].s]+g.e[i].c+tcost[g.e[i].g]==d&&scost[g.e[i].s]*2<d&&tcost[g.e[i].g]*2<d){
ans=(ans-scnt[g.e[i].s]*tcnt[g.e[i].g]%MOD*tcnt[g.e[i].g]%MOD*scnt[g.e[i].s]%MOD+MOD)%MOD;
}
}
printf("%lld\n",ans);
return 0;
}
Submission Info
Submission Time
2018-11-16 18:26:07+0900
Task
E - Avoiding Collision
User
kyopro_friends
Language
C (GCC 5.4.1)
Score
700
Code Size
3690 Byte
Status
AC
Exec Time
270 ms
Memory
30428 KB
Compile Error
./Main.c: In function ‘readgraph’:
./Main.c:69:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&m);
^
./Main.c:70:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&s,&t);
^
./Main.c:74:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&x,&y,&c);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
700 / 700
Status
Set Name
Test Cases
Sample
sample01.txt, sample02.txt, sample03.txt, sample04.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt
Case Name
Status
Exec Time
Memory
01.txt
AC
255 ms
30300 KB
02.txt
AC
262 ms
30300 KB
03.txt
AC
262 ms
30300 KB
04.txt
AC
265 ms
30300 KB
05.txt
AC
255 ms
30300 KB
06.txt
AC
200 ms
30336 KB
07.txt
AC
257 ms
30300 KB
08.txt
AC
136 ms
28324 KB
09.txt
AC
256 ms
30300 KB
10.txt
AC
252 ms
30300 KB
11.txt
AC
270 ms
30300 KB
12.txt
AC
254 ms
30300 KB
13.txt
AC
245 ms
30300 KB
14.txt
AC
259 ms
30300 KB
15.txt
AC
261 ms
30428 KB
16.txt
AC
253 ms
30300 KB
17.txt
AC
252 ms
30300 KB
18.txt
AC
270 ms
30300 KB
sample01.txt
AC
8 ms
22656 KB
sample02.txt
AC
9 ms
22656 KB
sample03.txt
AC
8 ms
22656 KB
sample04.txt
AC
8 ms
22656 KB