哇这些真题终于正经起来奥
刚看这道题很不自信觉得自己肯定不能建图成功甚至想过用贪心。。
后来一想发现建图还是蛮容易的，AI我是真的蠢
话说一本通真的很坑啊，把原题的保留1位改成了2
我把在洛谷AC的代码交上去查了好久才发现。。
（话说为什么把读入优化换成scanf效率快了一千倍。。）
#include<bits/stdc++.h> using namespace std; const int maxn=105; int n,s,t,A,B,T[maxn<<2]; double dis[maxn<<2]; bool book[maxn<<2]; /*inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') if(ch=='-') f=-1,ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f; }*/ struct data{ int city; int x,y; }a[maxn<<2]; inline int power_2(int x) { return x*x; } void getlast(int x1,int y1,int x2,int y2,int x3,int y3,int i) { int x4,y4; int dis1=power_2(x1-x2)+power_2(y1-y2), dis2=power_2(x1-x3)+power_2(y1-y3), dis3=power_2(x2-x3)+power_2(y2-y3); if(dis2==dis1+dis3) x4=x3-x2+x1,y4=y3+y1-y2; if(dis1==dis2+dis3) x4=x2-x3+x1,y4=y2+y1-y3; if(dis3==dis1+dis2) x4=x3-x1+x2,y4=y3+y2-y1; a[i+3].x=x4;a[i+3].y=y4; }//这道题目唯一需要注意的点大概就是这个求第四个点 inline double distance(int x1,int y1,int x2,int y2) { return sqrt(power_2(x1-x2)+power_2(y1-y2)); } void SPFA() { memset(book,0,sizeof(book)); queue <int> q; for(int i=1;i<=s<<2;i++) dis[i]=99999999; for(int i=A*4-3;i<=A*4;i++) dis[i]=0,q.push(i),book[i]=1; while(!q.empty()) { int u=q.front();q.pop();book[u]=0; for(int i=1;i<=s<<2;i++) { if(i==u) continue; double cost=distance(a[i].x,a[i].y,a[u].x,a[u].y); if(a[i].city==a[u].city) cost*=T[a[i].city]; else cost*=t; if(dis[i]>dis[u]+cost) { dis[i]=dis[u]+cost; if(!book[i]) { book[i]=1; q.push(i); } } } } } void init() { //memset(t,0,sizeof(t)); memset(a,0,sizeof(a)); scanf("%d%d%d%d",&s,&t,&A,&B); int i; for(i=1;i<=s<<2;i+=4) { //int x1,x2,x3,y1,y2,y3; scanf("%d%d%d%d%d%d%d",&a[i].x,&a[i].y,&a[i+1].x,&a[i+1].y,&a[i+2].x,&a[i+2].y,&T[i/4+1]); a[i].city=a[i+1].city=a[i+2].city=a[i+3].city=i/4+1; getlast(a[i].x,a[i].y,a[i+1].x,a[i+1].y,a[i+2].x,a[i+2].y,i); } } int main() { scanf("%d",&n); int i; for(i=1;i<=n;i++) { init(); SPFA(); double ans=dis[B<<2]; for(int j=B*4-3;j<B*4;j++) if(ans>dis[j]) ans=dis[j]; printf("%.2lf ",ans); } return 0; }