1 条题解
-
0
#include<bits/stdc++.h> #define INF 1010580540 using namespace std; const int M=205; int n,K,s,e,m,cnt,mp[1005]; struct Mat{int x,m[M][M];Mat(){x=1,memset(m,0x3f,sizeof(m));}}w; int ID(int x){return mp[x]?mp[x]:mp[x]=++cnt;} Mat operator*(Mat a,Mat b) { Mat c;c.x=a.x; for(int i=1;i<=a.x;i++) for(int j=1;j<=b.x;j++) for(int k=1;k<=a.x;k++) c.m[i][j]=min(c.m[i][j],a.m[i][k]+b.m[k][j]); return c; } Mat operator^(Mat a,int p) { Mat c;bool flag=true; for(;p;p>>=1,a=a*a) if(p&1) {if(flag) c=a,flag=false;else c=c*a;} return c; } void work() { Mat ans=w^K; printf("%d",ans.m[s][e]); } void init() { int x,y,z; scanf("%d%d%d%d",&K,&m,&s,&e); for(int i=1;i<=m;i++) { scanf("%d%d%d",&z,&x,&y); x=ID(x);y=ID(y); w.m[x][y]=w.m[y][x]=z; } s=ID(s);e=ID(e);w.x=cnt; } int main() { init(); work(); return 0; }
- 1
信息
- ID
- 1706
- 时间
- 500ms
- 内存
- 64MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 10
- 已通过
- 8
- 上传者