Dijkstra模板
int a[3010][3010],d[3010]; int n,m; bool v[3010]; void dijkstra() { memset(d,INF,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; for(int i=1; i<n; i++) { int x=0; for(int j=1; j<=n; j++) { if(!v[j] && (x==0 || d[j]<d[x])) x=j; } v[x]=1; for(int y=1; y<=n; y++) if(!v[y]) d[y]=min(d[y],d[x]+a[x][y]); } }