98 条题解

  • 4
    @ 2017-10-28 18:51:04

    绕一点的Floyed(〃・o・〃)

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int s,t,a,b,js=0;
    double ans,dis12,dis13,dis23,maxn=-1;
    double x[500],y[500],T[110],f[500][500];
    double dis(int a,int b)
    {
        return sqrt((x[b]-x[a])*(x[b]-x[a])+(y[b]-y[a])*(y[b]-y[a]));
    }
    int main()
    {
        cin>>s>>t>>a>>b;
        if(s==1)
        {
            cout<<"0.00";
            return 0;
        }
        for(int i=1;i<=s;++i)
        {
            for(int j=1;j<=3;++j)
            {
               js++;
               cin>>x[js]>>y[js];
            }
            cin>>T[i];
            dis12=dis(js-2,js-1);
            dis13=dis(js-2,js);
            dis23=dis(js-1,js);
            maxn=max(dis12,max(dis13,dis23));
            if(maxn==dis12)
            {
                x[js+1]=x[js-2]+x[js-1]-x[js];
                y[js+1]=y[js-2]+y[js-1]-y[js];
            }
            else if(maxn==dis13)
            {
                x[js+1]=x[js-2]+x[js]-x[js-1];
                y[js+1]=y[js-2]+y[js]-y[js-1];
            }
            else if(maxn==dis23)
            {
                x[js+1]=x[js-1]+x[js]-x[js-2];
                y[js+1]=y[js-1]+y[js]-y[js-2];
            }
            for(int k=1;k<=4;++k)
            {
                for(int j=1;j<=4;++j)
                {
                    f[js+k-3][js+j-3]=dis(js+k-3,js+j-3)*T[i];
                }
            }
            js++;
        }
        for(int i=1;i<=s;++i)
        {
            for(int j=i+1;j<=s;++j)
            {
                for(int o=1;o<=4;++o)
                {
                    for(int p=1;p<=4;++p)
                    {
                        int k1=(i-1)*4+o;
                        int k2=(j-1)*4+p;
                        f[k1][k2]=f[k2][k1]=dis(k1,k2)*t;
                    }
                }
            }       
        }
        for(int k=1;k<=s*4;++k)
        {
            for(int i=1;i<=s*4;++i)
            {
                for(int j=1;j<=s*4;++j)
                {
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
                }
            }
        }
        ans=1000000;
        for(int i=1;i<=4;++i)
        {
            for(int j=1;j<=4;++j)
            {
                int k1=(a-1)*4+i;
                int k2=(b-1)*4+j;
                ans=min(ans,f[k1][k2]);
            }
        }
        printf("%0.2lf",ans);
        return 0;
    }
    
  • 3
    @ 2017-09-29 23:07:29

    求出第四个点, 暴力跑 floyd.

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef pair<int, int> Vector;
    int _count, _time[100];
    double dist[400][400];
    Vector v[400];
    
    bool right_angle(Vector x, Vector y) {
        return x.first * y.first + x.second * y.second == 0;
    }
    
    double calc(Vector x, Vector y) {
        return sqrt(pow(1.0 * (x.first - y.first), 2) + pow(1.0 * (x.second - y.second), 2));
    }
    
    int main() {
        ios::sync_with_stdio(false);
        int s, t1, A, B, x1, y1, x2, y2, x3, y3, t2;
        cin >> s >> t1 >> A >> B;
        for (int i = 0; i < s; i++) {
            cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> t2;
            Vector x = Vector(x1 - x2, y1 - y2);
            Vector y = Vector(x1 - x3, y1 - y3);
            Vector z = Vector(x2 - x3, y2 - y3);
            Vector vec;
            if (right_angle(x, y)) {
                vec = Vector(x2 + x3 - x1, y2 + y3 - y1);
            } else if (right_angle(x, z)) {
                vec = Vector(x1 + x3 - x2, y1 + y3 - y2);
            } else {
                vec = Vector(x1 + x2 - x3, y1 + y2 - y3);
            }
            v[i * 4] = Vector(x1, y1);
            v[i * 4 + 1] = Vector(x2, y2);
            v[i * 4 + 2] = Vector(x3, y3);
            v[i * 4 + 3] = vec;
            _time[i] = t2;
        }
        for (int i = 0; i < 4 * s; i++) {
            for (int j = 0; j < 4 * s; j++) {
                if (i != j) {
                    if (j >= i / 4 * 4 && j < 4 * (i / 4 + 1)) {
                        dist[i][j] = _time[i / 4] * calc(v[i], v[j]);
                    } else {
                        dist[i][j] = t1 * calc(v[i], v[j]);
                    }
                }
            }
        }
        // floyd
        for (int k = 0; k < 4 * s; k++) {
            for (int i = 0; i < 4 * s; i++) {
                for (int j = 0; j < 4 * s; j++) {
                    if (i != j && j != k && i != k) {
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        double _min = 1e15;
        for (int i = 4 * (A - 1); i < 4 * A; i++) {
            for (int j = 4 * (B - 1); j < 4 * B; j++) {
                _min = min(_min, dist[i][j]);
            }
        }
        cout << setprecision(2) << fixed << _min << endl;
        return 0;
    }
    
  • 2
    @ 2018-08-07 16:35:14

    数据有double的题目都是坑,很多习惯的写法就会WA
    比如说松弛的时候总是写int to=g[i][j].to,w=g[i][j].w来获取目标点的属性,这样一来w设置成int,即使你存的是double也没用,也很难发现QAQ

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=10000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;
    
    int s,a,b;
    struct point {
        double x,y;
    } p[101][5];
    double cost;
    double c[101];
    double d[405];
    struct edge {
        int to;
        double w;
    };
    vector<edge> g[405];
    bool vis[405];
    double ans;
    void insert(int x,int y,double w) {
        g[x].pb(edge{y,w});
        g[y].pb(edge{x,w});
    }
    void Dijkstra() {
        REP(i,4*1+1,4*s+4) d[i]=1e18;
        FOR(i,4) {
            d[4*a+i]=0;
            //vis[4*a+i]=1;
        }
        REP(i,4*1+1,4*s+4) {
            int pos=0;
            REP(j,4*1+1,4*s+1) if (!vis[j]) {
                if (!pos||d[j]<d[pos]) pos=j;
            }
            if (pos) {
                vis[pos]=1;
                for (int j=0;j<g[pos].size();j++) {
                    int to=g[pos][j].to;
                    double w=g[pos][j].w;
                    if (d[to]>d[pos]+w) {
                        d[to]=d[pos]+w;
                    }
                } 
            }
        }
    }
    double dis(point a,point b) {
        double x1=a.x,y1=a.y;
        double x2=b.x,y2=b.y;
        return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>s>>cost>>a>>b;
        FOR(i,s) {
            FOR(j,3) cin>>p[i][j].x>>p[i][j].y;
            cin>>c[i];
            FOR(k1,3) FOR(k2,3) if (k1!=k2) {
                if (dis(p[i][k1],p[i][k2])>max(dis(p[i][6-k1-k2],p[i][k1]),dis(p[i][6-k1-k2],p[i][k2]))) {
                    double xx=p[i][k1].x+p[i][k2].x,yy=p[i][k1].y+p[i][k2].y;
                    double _x=xx-p[i][6-k1-k2].x,_y=yy-p[i][6-k1-k2].y;
                    p[i][4].x=_x,p[i][4].y=_y;
                }
            }
        }
        /*
        FOR(i,s) {
            FOR(j,4) cout<<p[i][j].x<<","<<p[i][j].y<<" ";
            cout<<endl;
        }*/
        FOR(i,s) {
            FOR(j,4) REP(k,j+1,4) insert(4*i+j,4*i+k,dis(p[i][j],p[i][k])*c[i]);
            FOR(j,4) REP(k,i+1,s) FOR(l,4) {
                insert(4*i+j,4*k+l,dis(p[i][j],p[k][l])*cost);
            }
        }
        Dijkstra();
        ans=1e18;
        FOR(i,4) ans=min(ans,d[4*b+i]);
        printf("%.2lf\n",ans);
        return 0;
    }
    
  • 1
    @ 2017-09-28 22:41:28

    随便搞搞

    #include <stdio.h>
    #include <vector>
    #include <string.h>
    #include <cmath>
    #include <queue>
    #define ID(i,j) (i-1)*4+j
    using namespace std;
    
    const int MAXN=105;
    const int SIZE=1e5+5;
    const int INF=0x3f3f3f3f;
    
    int T,S,A,B;
    
    struct Node{
        int x[6],y[6];
        int w;  
    }E[MAXN];
    
    void get(int op){
        
        int a=E[op].x[1],b=E[op].x[2],c=E[op].x[3];
        int d=E[op].y[1],e=E[op].y[2],f=E[op].y[3];
        
        int x1=E[op].x[1],y1=E[op].y[1];
        int x2=E[op].x[2],y2=E[op].y[2];
        int x3=E[op].x[3],y3=E[op].y[3];
        
        int d1=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
        int d2=(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3);
        int d3=(x3-x1)*(x3-x1)+(y3-y1)*(y3-y1);
        
        if(d1+d3==d2){
            int dx=b-a;
            int dy=e-d;
            E[op].x[4]=c+dx;
            E[op].y[4]=f+dy;
        }else if(d1+d2==d3){
            int dx=a-b;
            int dy=d-e;
            E[op].x[4]=c+dx;
            E[op].y[4]=f+dy;
        }else{
            int dx=b-c;
            int dy=e-f;
            E[op].x[4]=a+dx;
            E[op].y[4]=d+dy;
        }
        
    #ifdef DBG
        printf("city:%d\n",op);
        for(int i=1;i<=4;i++){
            printf("%d %d\n",E[op].x[i],E[op].y[i]);
        }
    #endif
    
    }
    
    struct Edge{
        int v,next;
        double w;
    }G[SIZE];
    int head[SIZE],Ecnt;
    
    double d[SIZE];
    int vis[SIZE];
    
    double Dis(int x1,int y1,int x2,int y2){
        
        int x=x1-x2;
        int y=y1-y2;
        double D=sqrt(x*x+y*y);
        return D;
        
    }
    
    void ADD(int u,int v,double w){
        
        G[++Ecnt]=(Edge){v,head[u],w};head[u]=Ecnt;
        G[++Ecnt]=(Edge){u,head[v],w};head[v]=Ecnt;
    }
    
    void solve(){
        
        for(int i=1;i<=S;i++){
            get(i);
        }
        
        for(int i=1;i<=S;i++){
            for(int j=1;j<=4;j++){
                for(int k=j+1;k<=4;k++){
                    double dis=Dis(E[i].x[j],E[i].y[j],E[i].x[k],E[i].y[k]);
                    ADD(ID(i,j),ID(i,k),dis*(double)E[i].w);
                }
            }
        }
        
        for(int a=1;a<=S;a++){
            for(int b=a+1;b<=S;b++){
                for(int i=1;i<=4;i++){
                    for(int j=1;j<=4;j++){
                        double dis=Dis(E[a].x[i],E[a].y[i],E[b].x[j],E[b].y[j]);
                        ADD(ID(a,i),ID(b,j),dis*(double)T);
                    }
                }
            }
        }
        
        for(int i=1;i<=ID(S,4);i++){
            d[i]=INF;
        }
    #ifdef DBG
        for(int i=1;i<=ID(S,4);i++){
            printf("%.2lf\n",d[i]);
        }
    #endif
        
        queue<int>q;
        for(int i=1;i<=4;i++){
            q.push(ID(A,i));
            vis[ID(A,i)]=1;
            d[ID(A,i)]=0;
        }
        while(!q.empty()){
            int u=q.front();q.pop();
            vis[u]=0;
            for(int i=head[u];i;i=G[i].next){
                int v=G[i].v;
                double w=G[i].w;
                if(d[v]>d[u]+w){
                    d[v]=d[u]+w;
                    if(vis[v]==0){
                        vis[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        
        double ans=INF;
        for(int i=1;i<=4;i++){
            ans=min(ans,d[ID(B,i)]);
        }
        
        printf("%.2lf",ans);
        
    }
    
    int main(){
        
        scanf("%d%d%d%d",&S,&T,&A,&B);
        for(int i=1;i<=S;i++){
            for(int j=1;j<=3;j++){
                scanf("%d%d",&E[i].x[j],&E[i].y[j]);
            }
            scanf("%d",&E[i].w);
        }
        
        solve();
        return 0; 
    }
    
  • 1
    @ 2017-05-15 08:42:13

    利用直角三角形的性质,暴力求解出第四个点,然后直接跑floyd

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <string>
    #include <map>
    #include <cstring>
    #include <ctime>
    #include <vector>
    #define inf 1e9
    #define ll long long
    #define For(i,j,k) for(int i=j;i<=k;i++)
    #define Dow(i,j,k) for(int i=k;i>=j;i--)
    using namespace std;
    double x[501],y[501],T[501];
    double f[501][501];
    int n,t,s,e;
    double dis(int tx,int ty)
    {
        return sqrt((x[tx]-x[ty])*(x[tx]-x[ty])+(y[tx]-y[ty])*(y[tx]-y[ty]));
    }
    int main()
    {
        scanf("%d%d%d%d",&n,&t,&s,&e);
        For(i,1,n)
        {
            For(j,1,3)
                scanf("%lf%lf",&x[(i-1)*4+j],&y[(i-1)*4+j]);
            int p1=(i-1)*4+1;
            double l1=dis(p1,p1+1),l2=dis(p1+1,p1+2),l3=dis(p1+2,p1);
            double ma=max(l1,max(l2,l3));
            if(ma==l1)
            {
                double px=(x[p1]+x[p1+1])/2,py=(y[p1]+y[p1+1])/2;
                double dx=x[p1+2]-px,dy=y[p1+2]-py;
                x[p1+3]=px-dx;y[p1+3]=py-dy;
            }
            else 
            if(ma==l2)
            {
                double px=(x[p1+2]+x[p1+1])/2,py=(y[p1+2]+y[p1+1])/2;
                double dx=x[p1]-px,dy=y[p1]-py;
                x[p1+3]=px-dx;y[p1+3]=py-dy;
            }
            else
            {
                double px=(x[p1+2]+x[p1])/2,py=(y[p1+2]+y[p1])/2;
                double dx=x[p1+1]-px,dy=y[p1+1]-py;
                x[p1+3]=px-dx;y[p1+3]=py-dy;
            }
            scanf("%lf",&T[i]);
            For(j,1,4)
                For(k,1,4)
                    f[p1+j-1][p1+k-1]=dis(p1+j-1,p1+k-1)*T[i];
        }
        For(i,1,n)
            For(j,i+1,n)
                For(i1,1,4)
                    For(j1,1,4)
                    {
                        int p1=(i-1)*4+i1,p2=(j-1)*4+j1;
                        f[p1][p2]=f[p2][p1]=dis(p1,p2)*t;
                    }
    
        int tot=n*4;
        For(k,1,tot)
            For(i,1,tot)
                For(j,1,tot)
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
        double ans=100000000;
        For(i,1,4)
            For(j,1,4)
            {
                int p1=(s-1)*4+i,p2=(e-1)*4+j;
                ans=min(ans,f[p1][p2]);
            }
        printf("%.2f",ans);
        system("pause");
    }
         
    
  • 1
    @ 2016-11-17 16:50:59
    #include <cstdio>
    #include <cstdlib>
    #include <queue>
    #include <vector>
    #include <map>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    void read(int &k)
    {
        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*10+ch-'0';ch=getchar();}
        k=x*f;
    }
    
    int n,s,t,nn;
    double T,ans=2000000000.0;
    int p[405],flag[405];
    double dis[405];
    struct node
    {
        double t;
        int x[5],y[5],id[5];
    }a[105];
    struct edge
    {
        int a,b,nt;
        double w;
    }e[80005*2];
    
    void addedge(int x,int y,double w)
    {
        nn++;e[nn].a=x;e[nn].b=y;e[nn].nt=p[x];p[x]=nn;e[nn].w=w;
        nn++;e[nn].a=y;e[nn].b=x;e[nn].nt=p[y];p[y]=nn;e[nn].w=w;
    }
    
    double dist(int x1,int y1,int x2,int y2)
    {
        return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    
    void freshpos(int x)
    {
        double dis12=dist(a[x].x[1],a[x].y[1],a[x].x[2],a[x].y[2]);
        double dis13=dist(a[x].x[1],a[x].y[1],a[x].x[3],a[x].y[3]);
        double dis23=dist(a[x].x[2],a[x].y[2],a[x].x[3],a[x].y[3]);
        double maxv=max(max(dis12,dis13),dis23);
        if(maxv==dis12)
        {
            a[x].x[4]=a[x].x[1]+a[x].x[2]-a[x].x[3];
            a[x].y[4]=a[x].y[1]+a[x].y[2]-a[x].y[3];
        }
        else if(maxv==dis13)
        {
            a[x].x[4]=a[x].x[1]+a[x].x[3]-a[x].x[2];
            a[x].y[4]=a[x].y[1]+a[x].y[3]-a[x].y[2];
        }
        else if(maxv==dis23)
        {
            a[x].x[4]=a[x].x[2]+a[x].x[3]-a[x].x[1];
            a[x].y[4]=a[x].y[2]+a[x].y[3]-a[x].y[1];
        }
        //printf("%d %d\n",a[x].x[4],a[x].y[4]);
    }
    
    void spfa(int x)
    {
        queue<int>q;
        q.push(x);
        for(int i=1;i<=4*n;i++)
            dis[i]=2000000000.0,flag[i]=0;
        dis[x]=0,flag[x]=1;
        while(!q.empty())
        {
            int k=q.front();q.pop();
            flag[k]=0;
            for(int i=p[k];i;i=e[i].nt)
            {
                int v=e[i].b;
                if(dis[v]>dis[k]+e[i].w)
                {
                    dis[v]=dis[k]+e[i].w;
                    if(!flag[v])
                    {
                        flag[v]=1;
                        q.push(v);
                    }
                }
            }
        }
    }
    
    void input()
    {
        read(n),scanf("%lf",&T),read(s),read(t);
        for(int i=1;i<=n;i++)
        {
            read(a[i].x[1]),read(a[i].y[1]),read(a[i].x[2]),read(a[i].y[2]),read(a[i].x[3]),read(a[i].y[3]),scanf("%lf",&a[i].t);
            freshpos(i);
        }
        //id是记录点的编号
        int tmp=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=4;j++,tmp++)
                a[i].id[j]=tmp;
    }
    
    void build()
    {
        //单个城市内建边
        for(int i=1;i<=n;i++)
        for(int j=1;j<=4;j++)
        for(int k=j+1;k<=4;k++)
            addedge(a[i].id[j],a[i].id[k],a[i].t*dist(a[i].x[j],a[i].y[j],a[i].x[k],a[i].y[k]));
    
        //多个城市间建边
        for(int i=1;i<=n;i++)
        for(int ii=1;ii<=4;ii++)
        for(int j=i+1;j<=n;j++)
        for(int jj=1;jj<=4;jj++)
            addedge(a[i].id[ii],a[j].id[jj],T*dist(a[i].x[ii],a[i].y[ii],a[j].x[jj],a[j].y[jj]));
    }
    
    void solve()
    {
        for(int i=1;i<=4;i++)
        {
            spfa(a[s].id[i]);
            for(int j=1;j<=4;j++)
                ans=min(ans,dis[a[t].id[j]]);
        }
        printf("%.2f\n",ans);
    }
    
    int main()
    {
        input();
        build();
        solve();
        return 0;
    }
    
  • 1
    @ 2016-10-24 14:29:27

    = = 这道题考的是求矩形的*第四个顶点*。。。

    测试数据 #0: Accepted, time = 0 ms, mem = 2080 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 2080 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 2080 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 2080 KiB, score = 20
    测试数据 #4: Accepted, time = 0 ms, mem = 2076 KiB, score = 20
    Accepted, time = 0 ms, mem = 2080 KiB, score = 100

  • 1
    @ 2016-04-18 23:30:10

    两位小数四舍五入就错了
    舍去两位以后就对了
    ```c++
    #include <cstdio>
    #include <cmath>
    #define INF 99999999.0
    //#define debug

    int n,A,B;
    float plane;
    float x[105][5];
    float y[105][5];
    float train[105];
    float map[450][450];

    float calc(float x1,float y1,float x2,float y2){
    float dx=x1-x2,dy=y1-y2;
    float re=dx*dx+dy*dy;
    re=sqrt(re);
    return re;
    }

    void init(){
    for(int i=1;i<=440;i++)
    for(int j=1;j<=440;j++)
    map[i][j]=INF;
    }

    void build(){
    init();
    scanf("%d%f%d%d",&n,&plane,&A,&B);
    for(int i=1;i<=n;i++){
    for(int j=1;j<=3;j++){
    scanf("%f",&x[i][j]);
    scanf("%f",&y[i][j]);
    }
    scanf("%f",&train[i]);

    }
    //第四点坐标 向量法
    float vx[5],vy[5];
    int corner;
    //v[1]:1-2 v[2]:1-3 v[3]:2-3
    for(int i=1;i<=n;i++){
    vx[1]=x[i][1]-x[i][2];
    vy[1]=y[i][1]-y[i][2];

    vx[2]=x[i][1]-x[i][3];
    vy[2]=y[i][1]-y[i][3];

    vx[3]=x[i][2]-x[i][3];
    vy[3]=y[i][2]-y[i][3];

    for(int v1=1;v1<=3;v1++)
    for(int v2=1;v2<=3;v2++){
    if(vx[v1]*vx[v2]+vy[v1]*vy[v2]==0.0){
    if(v1==1&&v2==2)
    corner=1;
    if(v1==1&&v2==3)
    corner=2;
    if(v1==2&&v2==3)
    corner=3;
    }
    }
    x[i][4]=x[i][1]+x[i][2]+x[i][3]-2*x[i][corner];
    y[i][4]=y[i][1]+y[i][2]+y[i][3]-2*y[i][corner];
    }

    float val;
    int c1,c2,n1,n2,x1,y1,x2,y2;
    for(int i=1;i<=4*n;i++)
    for(int j=1;j<=4*n;j++){
    c1=i/4+1;
    c2=j/4+1;
    n1=i%4;
    n2=j%4;
    if(n1==0){
    c1--;
    n1=4;
    }

    if(n2==0){
    c2--;
    n2=4;
    }

    x1=x[c1][n1];
    y1=y[c1][n1];
    x2=x[c2][n2];
    y2=y[c2][n2];

    if(c1==c2)
    val=train[c1]*calc(x1,y1,x2,y2);
    else
    val=plane*calc(x1,y1,x2,y2);

    map[i][j]=val;
    }
    }

    void floyd(){
    for(int k=1;k<=4*n;k++)
    for(int i=1;i<=4*n;i++)
    for(int j=1;j<=4*n;j++)
    if(map[i][k]+map[k][j]<map[i][j])
    map[i][j]=map[i][k]+map[k][j];
    }

    int main(){
    #ifdef debug
    freopen("in.txt","r",stdin);
    #endif
    build();
    floyd();

    float minn=INF;
    for(int i=1;i<=4;i++)
    for(int j=1;j<=4;j++){
    if(minn>map[(A-1)*4+i][(B-1)*4+j])
    minn=map[(A-1)*4+i][(B-1)*4+j];
    }
    printf("%.2f",minn);

    return 0;
    }
    ```

  • 1
    @ 2016-03-10 23:42:44
    uses math;
    var s,t,a,b:longint;
      i,x,y,z:longint;
      res:real;
      e:array[1..3,1..2] of longint;
      air:array[0..500,1..2] of longint; //机场
      cost:array[0..500] of longint; //城市铁路价格
      mc:array[0..500,0..500] of real; //最短路
    
    function dis(x,y:longint):real;
    var d:real;
    begin
      d:=sqrt(sqr(air[x,1]-air[y,1])+sqr(air[x,2]-air[y,2]));
      if ((x-1) div 4)=((y-1) div 4) then dis:=d*cost[((x-1) div 4)+ 1]
      else dis:=d*t;
    end;
    
    begin
      //预处理
      read(s,t,a,b);
      for i:=1 to s do begin
        read(air[i*4-3,1],air[i*4-3,2],air[i*4-2,1],air[i*4-2,2],
             air[i*4-1,1],air[i*4-1,2],cost[i]);
        //三边向量
        e[1,1]:=air[i*4-3,1]-air[i*4-2,1];
        e[1,2]:=air[i*4-3,2]-air[i*4-2,2];
        e[2,1]:=air[i*4-2,1]-air[i*4-1,1];
        e[2,2]:=air[i*4-2,2]-air[i*4-1,2];
        e[3,1]:=air[i*4-1,1]-air[i*4-3,1];
        e[3,2]:=air[i*4-1,2]-air[i*4-3,2];
        //判直角顶点(x)
        if (e[1,1]*e[2,1]+e[1,2]*e[2,2])=0 then begin x:=i*4-2;y:=i*4-1;z:=i*4-3 end
        else if (e[2,1]*e[3,1]+e[2,2]*e[3,2])=0 then begin x:=i*4-1;y:=i*4-2;z:=i*4-3 end
        else begin x:=i*4-3;y:=i*4-1;z:=i*4-2 end;
        //计算第四点坐标
        air[i*4,1]:=air[y,1]+air[z,1]-air[x,1];
        air[i*4,2]:=air[y,2]+air[z,2]-air[x,2];
      end;
    
      //floyd
      s:=s*4;
      for x:=1 to s do
        for y:=1 to s do
          if x=y then mc[x,y]:=0 else mc[x,y]:=1000000;
      for x:=1 to s do
        for y:=1 to s do
          mc[x,y]:=dis(x,y);
      for z:=1 to s do
        for x:=1 to s do
          for y:=1 to s do
            mc[x,y]:=min(mc[x,y],mc[x,z]+mc[z,y]);
    
      res:=1000000;
      for x:=a*4-3 to a*4 do
        for y:=b*4-3 to b*4 do
          res:=min(res,mc[x,y]);
      write(res:7:2);
    end.
    
  • 0
    @ 2015-10-29 14:43:07

    此题第一个点坑爹,居然只有一个城市,从自己走到自己,费用为0。把代码里一个else去掉就过了...

  • 0
    @ 2015-10-09 19:31:06

    vijos的评测姬好坑啊,因为double用%lf输出卡了WA三题了。。。2015初赛前一天合影留念
    #include<cstdio>
    #include<iostream>
    #include<queue>
    #include<cmath>
    #include<cstring>
    struct point{
    long x;
    long y;
    bool operator <(const point a) const{
    return x<a.x;
    }
    };
    struct city{
    point air[4];
    long t;
    city(){
    air[3].x=32679;
    air[3].y=32679;
    }
    };
    struct edge{
    long num;
    long airm;
    double dis;
    bool operator < (const edge a) const{
    return dis>a.dis;
    }
    };
    double get_dis(point a,point b)
    {
    return sqrt((double)((a.x-b.x)*(a.x-b.x))+(double)((a.y-b.y)*(a.y-b.y)));
    }
    std::priority_queue<edge> q;
    city c[110];
    int main()
    {
    std::ios::sync_with_stdio(false);
    long s,t,A,B;
    std::cin>>s>>t>>A>>B;
    double ans(32679);

    int maxk(0),maxj(0),l;
    double max(0);
    point mid;
    for(int i=1;i<=s;i++)
    {
    for(int j=0;j<3;j++)
    std::cin>>c[i].air[j].x>>c[i].air[j].y;
    std::cin>>c[i].t;
    for(int j=0;j<3;j++)
    for(int k=0;k<3;k++)
    if(get_dis(c[i].air[j],c[i].air[k])>max)
    {
    max=get_dis(c[i].air[j],c[i].air[k]);
    maxk=k;
    maxj=j;
    }
    max=0;
    l=3-maxk-maxj;
    //printf("%d %d %d",maxk,maxj,l);
    mid.x=c[i].air[maxj].x+c[i].air[maxk].x;
    mid.y=c[i].air[maxj].y+c[i].air[maxk].y;
    c[i].air[3].x=mid.x-c[i].air[l].x;
    c[i].air[3].y=mid.y-c[i].air[l].y;//找对角线然后构造矩形,讲道理啊真是麻烦
    // std::cout<<std::endl;
    }
    bool v[s+10][4];
    double d[110][4];
    edge u;
    for(int i=0;i<4;i++)//迪杰斯特拉
    {
    for(int m=0;m<110;m++)
    for(int w=0;w<4;w++)
    d[m][w]=32679;
    memset(v,0,sizeof(v));
    q.push((edge){A,i,0});
    d[A][i]=0;
    while(!q.empty())
    {
    u=q.top();
    q.pop();
    if(v[u.num][u.airm]) continue;
    v[u.num][u.airm]=true;
    for(int j=1;j<=s;j++)
    for(int k=0;k<4;k++)
    {
    if(j!=u.num)
    {{
    if(d[j][k]>d[u.num][u.airm]+get_dis(c[j].air[k],c[u.num].air[u.airm])*t)
    d[j][k]=d[u.num][u.airm]+get_dis(c[j].air[k],c[u.num].air[u.airm])*t;
    q.push((edge){j,k,d[j][k]}); }}
    else if(d[j][k]>d[u.num][u.airm]+get_dis(c[j].air[k],c[u.num].air[u.airm])*c[j].t)
    {
    d[j][k]=d[u.num][u.airm]+get_dis(c[j].air[k],c[u.num].air[u.airm])*c[j].t;
    q.push((edge){j,k,d[j][k]});}
    }
    }
    for(int k=0;k<4;k++)
    if(d[B][k]<ans)
    ans=d[B][k];
    }
    printf("%.2lf",ans);
    }

  • 0
    @ 2015-09-19 20:02:16

    醉了
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<vector>
    #include<queue>
    #include<fstream>
    using namespace std;
    const int inf=1e9;
    int N,city_num,S,T;
    int fly_cost;
    int tot;
    struct node{
    int x[5],y[5];
    }Airport[200];
    int road_cost[200];
    int vis[200][200];
    int to[200][200];
    double cost[200][200];
    double ANS;
    int min1(double a1,double a2){
    if(a1<a2) return a1;
    else return a2;
    }
    void calc_roadcost(int xx){//计算机场之间的铁路费用,xx表示机场标号

    for(int i=1;i<=4;i++){//机场标号
    int u=4*(xx-1)+i;//在图中代表的点的标号
    for(int j=1;j<=4;j++){//机场标号
    int v=4*(xx-1)+j;//在图中代表的点的标号
    if(u!=v&&vis[u][v]==0&&vis[v][u]==0){//如果不是同一个点,且没有建立过连接
    vis[u][v]=1; vis[v][u]=1;
    int e=++to[u][0];
    int r=++to[v][0];
    to[u][e]=v; to[v][r]=u;

    double dis=((double)Airport[xx].x[i]-(double)Airport[xx].x[j])*((double)Airport[xx].x[i]-(double)Airport[xx].x[j])+
    ((double)Airport[xx].y[i]-(double)Airport[xx].y[j])*((double)Airport[xx].y[i]-(double)Airport[xx].y[j]);
    dis=sqrt(dis);
    dis*=(double)road_cost[xx];
    cost[u][e]=dis; cost[v][r]=dis;
    }
    }
    }

    }

    void calc_fly_cost(){//计算机场之间的航线费用

    for(int i=1;i<=city_num;i++){//城市标号
    for(int j=1;j<=4;j++){//城市中的机场
    int u=4*(i-1)+j;//此机场在图中的标号
    for(int k=1;k<=city_num;k++){//城市标号
    if(k!=i){//保证不是同一个城市
    for(int t=1;t<=4;t++){//城市中的机场
    int v=4*(k-1)+t;//此机场在图中的标号

    if(vis[u][v]==0&&vis[v][u]==0){//没有建立过连接
    vis[u][v]=1; vis[v][u]=1;
    int e=++to[u][0];
    int r=++to[v][0];

    to[u][e]=v; to[v][r]=u;
    double dis=sqrt(((double)Airport[i].x[j]-(double)Airport[k].x[t])*((double)Airport[i].x[j]-(double)Airport[k].x[t])+
    ((double)Airport[i].y[j]-(double)Airport[k].y[t])*((double)Airport[i].y[j]-(double)Airport[k].y[t]));
    dis*=(double)fly_cost;
    cost[u][e]=dis; cost[v][r]=dis;

    }
    else continue;
    }
    }
    else continue;
    }
    }
    }

    }
    void SPFA(int s){

    static queue<int> Q;
    double dis[200];
    bool vis2[200];

    for(int i=0;i<=199;i++) dis[i]=(double)inf;
    memset(vis2,false,sizeof(vis2));
    while(Q.size()>0) Q.pop();

    dis[s]=(double)0;
    Q.push(s); vis2[s]=true;

    while(Q.size()>0){
    int x=Q.front(); Q.pop();
    vis2[x]=false;
    for(int i=1;i<=to[x][0];i++){
    int y=to[x][i];
    if(dis[y]>dis[x]+cost[x][i]){
    dis[y]=dis[x]+cost[x][i];
    if(vis2[y]==false){
    vis2[y]=true;
    Q.push(y);
    }
    }
    }
    }

    for(int i=1;i<=4;i++){
    int v=4*(T-1)+i;
    if(dis[v]<(double)ANS){
    ANS=dis[v];
    }
    }

    }
    inline double calc_dis(int x1,int x2,int y1,int y2){//两点间距离的平方
    return ((double)x1-(double)x2)*((double)x1-(double)x2)+
    ((double)y1-(double)y2)*((double)y1-(double)y2);
    }
    int main(){
    scanf("%d%d%d%d",&city_num,&fly_cost,&S,&T);
    tot=4*city_num;
    for(int j=1;j<=city_num;j++){
    scanf("%d%d%d%d%d%d%d",&Airport[j].x[1],&Airport[j].y[1],
    &Airport[j].x[2],&Airport[j].y[2],
    &Airport[j].x[3],&Airport[j].y[3],
    &road_cost[j]);

    if(calc_dis(Airport[j].x[1],Airport[j].x[2],Airport[j].y[1],Airport[j].y[2])==
    calc_dis(Airport[j].x[1],Airport[j].x[3],Airport[j].y[1],Airport[j].y[3])+
    calc_dis(Airport[j].x[2],Airport[j].x[3],Airport[j].y[2],Airport[j].y[3])
    )//说明 3是直角顶点
    Airport[j].x[4]=Airport[j].x[1]+Airport[j].x[2]-Airport[j].x[3],
    Airport[j].y[4]=Airport[j].y[1]+Airport[j].y[2]-Airport[j].y[3];

    else if(calc_dis(Airport[j].x[1],Airport[j].x[3],Airport[j].y[1],Airport[j].y[3])==
    calc_dis(Airport[j].x[1],Airport[j].x[2],Airport[j].y[1],Airport[j].y[2])+
    calc_dis(Airport[j].x[3],Airport[j].x[2],Airport[j].y[3],Airport[j].y[2])
    )//说明 2是直角顶点
    Airport[j].x[4]=Airport[j].x[1]+Airport[j].x[3]-Airport[j].x[2],
    Airport[j].y[4]=Airport[j].y[1]+Airport[j].y[3]-Airport[j].y[2];

    else if(calc_dis(Airport[j].x[2],Airport[j].x[3],Airport[j].y[2],Airport[j].y[3])==
    calc_dis(Airport[j].x[2],Airport[j].x[1],Airport[j].y[2],Airport[j].y[1])+
    calc_dis(Airport[j].x[3],Airport[j].x[1],Airport[j].y[3],Airport[j].y[1])
    )//说明 1是直角顶点
    Airport[j].x[4]=Airport[j].x[2]+Airport[j].x[3]-Airport[j].x[1],
    Airport[j].y[4]=Airport[j].y[2]+Airport[j].y[3]-Airport[j].y[1];

    calc_roadcost(j);//计算机场之间的铁路费用
    }
    calc_fly_cost();//计算机场之间的航线费用
    ANS=inf;
    for(int i=1;i<=4;i++){
    int from=4*(S-1)+i;
    SPFA(from);
    }
    printf("%.2f",ANS);
    return 0;
    }

  • 0
    @ 2015-07-17 19:12:47

    //100题留念
    ###include <iostream>
    ###include <queue>
    ###include <iomanip>
    ###include <cmath>
    ###include <cstdio>
    using namespace std;
    #define MAXN 105
    short S,t,A,B;
    struct Point
    {
    short X,Y;

    inline Point operator - (const Point& rhs) const
    {
    Point ret=*this;
    ret.X-=rhs.X;
    ret.Y-=rhs.Y;
    return ret;
    }
    inline short operator * (const Point& rhs) const
    {
    return X*rhs.X+Y*rhs.Y;
    }
    inline Point operator + (const Point &rhs) const
    {
    Point ret=*this;
    ret.X+=rhs.X;
    ret.Y+=rhs.Y;
    return ret;
    }

    inline friend istream& operator >> (istream &is, Point &rhs)
    {
    scanf("%d%d",&rhs.X,&rhs.Y);
    return is;
    }
    inline friend ostream& operator << (ostream &os, Point &rhs)
    {
    printf("%d %d",rhs.X,rhs.Y);
    return os;
    }
    }input[MAXN][4],a[2],b[2];
    double Abs(const Point &x)
    {
    return sqrt((double)x.X*(double)x.X+(double)x.Y*(double)x.Y);
    }
    char idx;
    void FindFour(const char &index)
    {

    for(char i=0;i<3;i++)
    {
    idx=0;
    for(char j=0;j<3;j++)
    {
    if(i==j) continue;
    a[idx]=input[index][j]-input[index][i];
    b[idx++]=input[index][j];
    }
    if(a[0]*a[1] == 0)
    {
    input[index][3]=b[0]+b[1]-input[index][i];
    break;
    }
    }
    }
    short train;
    struct edge
    {
    int to;
    double weight;
    edge* next;
    }*edges[MAXN*4],edgep[16*MAXN*MAXN],*allo=edgep;
    int V,E;
    void add_edge(const short &from,const short &to,const double &weight)
    {
    allo->to=to;
    allo->weight=weight;
    allo->next=edges[from];
    edges[from]=allo++;
    }
    double _d;
    void MakeInnerGraph(const short &index)
    {
    for(char i=0;i<3;i++)
    {
    for(char j=i+1;j<4;j++)
    {
    _d=Abs(input[index][j]-input[index][i])*(double)train;
    add_edge(index*4+i,index*4+j,_d);
    add_edge(index*4+j,index*4+i,_d);;
    }
    }
    }
    void MakeOuterGraph(const short &index)
    {
    for(char i=0;(++i)<index;)
    {
    for(char j=0;j<4;j++)
    {
    for(char k=0;k<4;k++)
    {
    _d=Abs(input[index][k]-input[i][j])*(double)t;
    add_edge(index*4+k,i*4+j,_d);
    add_edge(i*4+j,index*4+k,_d);
    }
    }
    }
    }
    double dist[MAXN*4];
    queue<short> q;
    bool vis[MAXN*4];
    short Head,Next;
    void PreSPFA()
    {
    for(short i=0,r=MAXN*4;i<r;i++)
    {
    dist[i]=10000.0;
    }
    for(char i=0;i<4;i++)
    {
    vis[A*4+i]=1;
    dist[A*4+i]=0.0;
    q.push(A*4+i);
    }
    }
    void SPFA()
    {
    PreSPFA();
    while(!q.empty())
    {
    Head=q.front();
    q.pop();
    for(edge *i=edges[Head];i;i=i->next)
    {
    Next=i->to;
    if(dist[Next] > (dist[Head]+i->weight))
    {
    dist[Next]=dist[Head]+i->weight;
    if(!vis[Next])
    {
    vis[Next]=1;
    q.push(Next);
    }
    }
    }
    vis[Head]=0;
    }
    }
    double ChooseSmallest()
    {
    double ret=10000.0;
    for(int i=0;i<4;i++)
    {
    ret=min(ret,dist[B*4+i]);
    }
    return ret;
    }
    void Print(const double &ans)
    {
    cout<<showpoint<<fixed<<setprecision(2)<<ans<<endl;
    }
    int main()
    {
    cin>>S>>t>>A>>B;
    if(S==1)
    {
    cout<<showpoint<<fixed<<setprecision(2)<<0.0<<endl;
    return 0;
    }
    for(char i=0;(i++)<S;)
    {
    for(char j=0;j<3;j++)
    cin>>input[i][j];
    FindFour(i);
    cin>>train;
    MakeInnerGraph(i);
    MakeOuterGraph(i);
    }
    SPFA();
    Print(ChooseSmallest());
    return 0;
    }

  • 0
    @ 2014-11-02 13:29:20

    你这磨人的最短路
    #include <iostream>
    #include <vector>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    int S,A,B,T;
    const int INF=1000000000;
    double ans=INF;
    double G[400+5][400+5];
    double spfa(int,int);
    struct city
    {
    int t;
    int x[4];
    int y[4];
    city():t(0)
    {
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    }
    };
    city m[100+5];
    inline double distance(int a,int b,int h1,int h2)
    {
    return sqrt(pow(m[a].x[h1]-m[b].x[h2],2)+pow(m[a].y[h1]-m[b].y[h2],2));
    }
    int main()
    {
    for(int i=0;i!=400+5;++i)
    for(int j=0;j!=400+5;++j)
    G[i][j]=INF;
    scanf("%d%d%d%d",&S,&T,&A,&B);
    //problem
    for(int i=1;i<=S;++i)
    {
    city &p=m[i];
    cin>>p.x[0]>>p.y[0]>>p.x[1]>>p.y[1]>>p.x[2]>>p.y[2]>>p.t;
    if((p.x[0]-p.x[1])*(p.x[1]-p.x[2])+(p.y[0]-p.y[1])*(p.y[1]-p.y[2])==0)
    {
    p.x[3]=p.x[0]+p.x[2]-p.x[1];
    p.y[3]=p.y[0]+p.y[2]-p.y[1];
    }
    if((p.x[0]-p.x[1])*(p.x[0]-p.x[2])+(p.y[0]-p.y[1])*(p.y[0]-p.y[2])==0)
    {
    p.x[3]=p.x[1]+p.x[2]-p.x[0];
    p.y[3]=p.y[1]+p.y[2]-p.y[0];
    }

    if((p.x[1]-p.x[2])*(p.x[0]-p.x[2])+(p.y[1]-p.y[2])*(p.y[0]-p.y[2])==0)
    {
    p.x[3]=p.x[0]+p.x[1]-p.x[2];
    p.y[3]=p.y[0]+p.y[1]-p.y[2];
    }
    }
    for(int p=1;p<=S;++p)
    {
    int i=(p-1)*4+1;
    G[i][i+1]=distance(p,p,0,1)*m[p].t;
    G[i][i+2]=distance(p,p,0,2)*m[p].t;
    G[i][i+3]=distance(p,p,0,3)*m[p].t;
    //
    G[i+1][i]=distance(p,p,1,0)*m[p].t;
    G[i+1][i+2]=distance(p,p,1,2)*m[p].t;
    G[i+1][i+3]=distance(p,p,1,3)*m[p].t;
    //
    G[i+2][i]=distance(p,p,2,0)*m[p].t;
    G[i+2][i+1]=distance(p,p,2,1)*m[p].t;
    G[i+2][i+3]=distance(p,p,2,3)*m[p].t;
    //
    G[i+3][i]=distance(p,p,3,0)*m[p].t;
    G[i+3][i+1]=distance(p,p,3,1)*m[p].t;
    G[i+3][i+2]=distance(p,p,3,2)*m[p].t;
    }
    for(int p=1;p<=S;++p)
    for(int k=p+1;k<=S;++k)
    {
    int i=(p-1)*4+1;
    int j=(k-1)*4+1;
    G[i][j]=distance(p,k,0,0)*T;
    G[j][i]=distance(p,k,0,0)*T;
    G[i+1][j]=distance(p,k,1,0)*T;
    G[j][i+1]=distance(p,k,1,0)*T;
    G[i+2][j]=distance(p,k,2,0)*T;
    G[j][i+2]=distance(p,k,2,0)*T;
    G[i+3][j]=distance(p,k,3,0)*T;
    G[j][i+3]=distance(p,k,3,0)*T;
    //
    G[i][j+1]=distance(p,k,0,1)*T;
    G[j+1][i]=distance(p,k,0,1)*T;
    G[i+1][j+1]=distance(p,k,1,1)*T;
    G[j+1][i+1]=distance(p,k,1,1)*T;
    G[i+2][j+1]=distance(p,k,2,1)*T;
    G[j+1][i+2]=distance(p,k,2,1)*T;
    G[i+3][j+1]=distance(p,k,3,1)*T;
    G[j+1][i+3]=distance(p,k,3,1)*T;
    //
    G[i][j+2]=distance(p,k,0,2)*T;
    G[j+2][i]=distance(p,k,0,2)*T;
    G[i+1][j+2]=distance(p,k,1,2)*T;
    G[j+2][i+1]=distance(p,k,1,2)*T;
    G[i+2][j+2]=distance(p,k,2,2)*T;
    G[j+2][i+2]=distance(p,k,2,2)*T;
    G[i+3][j+2]=distance(p,k,3,2)*T;
    G[j+2][i+3]=distance(p,k,3,2)*T;
    //
    G[i][j+3]=distance(p,k,0,3)*T;
    G[j+3][i]=distance(p,k,0,3)*T;
    G[i+1][j+3]=distance(p,k,1,3)*T;
    G[j+3][i+1]=distance(p,k,1,3)*T;
    G[i+2][j+3]=distance(p,k,2,3)*T;
    G[j+3][i+2]=distance(p,k,2,3)*T;
    G[i+3][j+3]=distance(p,k,3,3)*T;
    G[j+3][i+3]=distance(p,k,3,3)*T;
    }

    for(int i=1;i<=4;++i)
    for(int j=1;j<=4;++j)
    {
    int a=(A-1)*4+i;
    int b=(B-1)*4+j;
    ans=min(ans,spfa(a,b));
    }
    printf("%.2f\n",ans);
    return 0;
    }

    double spfa(int f,int t)
    {
    queue<int> q;
    double d[400+5];
    int inq[400+5];
    for(int i=0;i!=400+5;++i)
    d[i]=INF;
    memset(inq,0,sizeof(inq));
    d[f]=0;
    inq[f]=1;
    q.push(f);
    while(q.empty()!=true)
    {
    int x=q.front();
    q.pop();
    inq[x]=0;
    for(int i=1;i<=400+5;++i)
    if(G[x][i]!=INF)
    {
    if(d[x]+G[x][i]<d[i])
    {
    d[i]=d[x]+G[x][i];
    if(inq[i]==0)
    {
    inq[i]=1;
    q.push(i);
    }
    }
    }
    }
    return d[t];
    }

  • 0
    @ 2014-10-27 16:53:43

    NOIP2014赛前AC留念
    (竟然卡了半个小时在预处理上……)
    var posx,posy:array[0..400] of longint;
    cost:array[0..401,0..401] of real;
    dist:array[0..401] of real;
    use:array[0..401] of boolean;
    s,t,a,b,i,j,k,tip,x1,x2,x3,x4,y1,y2,y3,y4,t1:longint;
    ans:real;
    procedure dijkstra;
    var i,j,pos:longint;
    min:real;
    begin
    for i:=1 to tip do
    begin
    min:=maxlongint;
    for j:=1 to tip do
    if not use[j] then
    if dist[j]<min then
    begin
    min:=dist[j];
    pos:=j;
    end;
    use[pos]:=true;
    for j:=1 to tip do
    if cost[pos,j]+dist[pos]<dist[j] then dist[j]:=cost[pos,j]+dist[pos];
    end;
    end;

    begin
    //assign(input,'t2.in');
    //assign(output,'t2.out');
    //reset(input);
    //rewrite(output);
    readln(s,t,a,b);
    for i:=1 to s do
    begin
    readln(x1,y1,x2,y2,x3,y3,t1);
    if (x2<>x3) and (x1<>x2) and (x1<>x3) then
    begin

    if ((y2-y1)*(y3-y1))/((x2-x1)*(x3-x1))=-1 then
    begin
    x4:=x3+x2-x1;
    y4:=y3+y2-y1;
    if ((y4-y3)*(y4-y2))/((x4-x3)*(x4-x2))<>-1 then
    begin
    x4:=x3+x1-x2;
    y4:=y3+y1-y2;
    end;
    end;

    if ((y3-y2)*(y1-y2))/((x3-x2)*(x1-x2))=-1 then
    begin
    x4:=x1+x3-x2;
    y4:=y1+y3-y2;
    if ((y4-y1)*(y4-y3))/((x4-x3)*(x4-x1))<>-1 then
    begin
    x4:=x1+x2-x3;
    y4:=y1+y2-y3;
    end;
    end;

    if ((y2-y3)*(y1-y3))/((x2-x3)*(x1-x3))=-1 then
    begin
    x4:=x1+x2-x3;
    y4:=y1+y2-y3;
    if ((y4-y1)*(y4-y2))/((x4-x1)*(x4-x2))<>-1 then
    begin
    x4:=x1+x3-x2;
    y4:=y3+y3-y2;
    end;
    end;

    end
    else
    begin
    if x1=x2 then x4:=x3;
    if x2=x3 then x4:=x1;
    if x1=x3 then x4:=x2;
    if y1=y2 then y4:=y3;
    if y1=y3 then y4:=y2;
    if y2=y3 then y4:=y1;
    end;
    inc(tip);
    posx[tip]:=x1;
    posy[tip]:=y1;
    inc(tip);
    posx[tip]:=x2;
    posy[tip]:=y2;
    inc(tip);
    posx[tip]:=x3;
    posy[tip]:=y3;
    inc(tip);
    posx[tip]:=x4;
    posy[tip]:=y4;
    for j:=tip-3 to tip do
    for k:=tip-3 to tip do
    if j<>k then cost[j,k]:=t1*(sqrt(sqr(posx[j]-posx[k])+sqr(posy[j]-posy[k])));
    end;
    for j:=1 to tip do
    for k:=1 to tip do
    if j<>k then
    if cost[j,k]=0 then cost[j,k]:=t*(sqrt(sqr(posx[j]-posx[k])+sqr(posy[j]-posy[k])));
    for i:=1 to tip do
    dist[i]:=maxlongint;
    for i:=a*4-3 to a*4 do dist[i]:=0;
    dijkstra;
    ans:=maxlongint;
    for i:=b*4-3 to b*4 do
    if dist[i]<ans then ans:=dist[i];
    writeln(ans:0:2);
    //close(input);
    //close(output);
    end.

  • 0
    @ 2014-10-15 17:16:19

    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    struct sb
    {
    int x,y,c;
    }pos[2001];
    bool b[201];
    double d[101];
    int n,tot,costf,st,ed,x[5],y[5],costt[201];
    double dis(int x,int y)
    {
    double k;
    k=sqrt(pow(pos[x].x-pos[y].x,2)+pow(pos[x].y-pos[y].y,2));
    if(pos[x].c==pos[y].c)
    k*=costt[pos[x].c];
    else
    k*=costf;
    return k;
    }
    double dij(int st)
    {
    double min,k;
    int i,j,p;
    memset(b,0,sizeof(b));
    memset(d,100,sizeof(d));
    d[st]=0;
    for(i=1;i<=tot;i++)
    {
    min=1e38;
    for(j=1;j<=tot;j++)
    if(!b[j]&&d[j]<min)
    {
    min=d[j];
    p=j;
    }
    b[p]=1;
    for(j=1;j<=tot;j++)
    if(!b[j])
    d[j]=d[j]>d[p]+dis(p,j)?d[p]+dis(p,j):d[j];
    }
    k=1e38;
    for(i=1;i<=tot;i++)
    {
    if(pos[i].c==ed)
    for(j=0;j<=3;j++)
    k=d[i+j]<k?d[i+j]:k;
    if(pos[i].c==ed)
    break;
    }
    return k;
    }
    main()
    {
    double min=1e38;
    int i,j,k;
    cin>>n>>costf>>st>>ed;
    for(i=1;i<=n;i++)
    {
    cin>>x[1]>>y[1]>>x[2]>>y[2]>>x[3]>>y[3]>>costt[i];
    for(j=1;j<=3;j++)
    for(k=1;k<=3;k++)
    if(j!=k&&(x[j]-x[k])*(x[6-k-j]-x[j])+(y[j]-y[k])*(y[6-k-j]-y[j])==0)
    {
    x[4]=x[k]+x[6-k-j]-x[j];
    y[4]=y[k]+y[6-k-j]-y[j];
    }
    for(j=1;j<=4;j++)
    {
    pos[++tot].x=x[j];
    pos[tot].y=y[j];
    pos[tot].c=i;
    }
    }
    for(i=1;i<=tot;i++)
    {
    if(pos[i].c==st)
    for(j=0;j<=3;j++)
    min=dij(i+j)<min?dij(i+j):min;
    if(pos[i].c==st)
    break;
    }
    printf("%.2lf",min);
    }

  • 0
    @ 2014-10-02 17:09:23

    type
    hhh=record
    x,y,c:longint;
    end;
    var
    n,tt,a,b,i,j,k,tot:longint;
    tem,min:extended;
    qh:array[0..500] of hhh;
    t:array[0..100] of longint;
    d:array[0..100] of extended;
    bb:array[0..100] of boolean;
    x,y:array[1..4] of longint;
    function dis(x,y:longint):extended;
    begin
    dis:=sqrt(sqr(qh[x].x-qh[y].x)+sqr(qh[x].y-qh[y].y));
    if qh[x].c=qh[y].c then
    dis:=dis*t[qh[x].c]
    else
    dis:=dis*tt;
    end;
    function dij(x:longint):extended;
    var
    i,jj,j:longint;
    min:extended;
    begin
    fillchar(bb,sizeof(bb),false);
    for i:=1 to tot do d[i]:=99999999;
    d[x]:=0; //writeln('!!!!!!!!');
    for i:=1 to tot do
    begin
    min:=99999999;
    for j:=1 to tot do
    if (not bb[j])and(d[j]<min) then
    begin
    min:=d[j];
    jj:=j; //writeln(jj);
    end;
    bb[jj]:=true;
    for j:=1 to tot do if (not bb[j]) and (dis(jj,j)+d[jj]<d[j]) then d[j]:=dis(jj,j)+d[jj];
    end; //writeln('!!!!!!!!');
    dij:=99999999;
    for i:=1 to tot do
    begin
    if qh[i].c=b then
    for j:=0 to 3 do
    if d[i+j]<dij then dij:=d[i+j];
    if qh[i].c=b then break;
    end;
    // writeln('!!!!!!!!');
    end;

    begin
    readln(n,tt,a,b);
    for i:=1 to n do
    begin
    readln(x[1],y[1],x[2],y[2],x[3],y[3],t[i]);
    for j:=1 to 3 do
    for k:=1 to 3 do
    if j<>k then
    if (x[j]-x[k])*(x[6-j-k]-x[j])+(y[j]-y[k])*(y[6-j-k]-y[j])=0 then
    begin
    x[4]:=x[k]+x[6-j-k]-x[j];
    y[4]:=y[k]+y[6-j-k]-y[j];
    //writeln(x[4],' ',y[4]);
    end;
    // writeln(x[4],y[4]);
    for j:=1 to 4 do
    begin
    inc(tot);
    qh[tot].x:=x[j];
    qh[tot].y:=y[j];
    qh[tot].c:=i;
    end;
    end;
    //writeln(x[4],y[4]);
    min:=99999999;
    for i:=1 to tot do
    begin
    if qh[i].c=a then
    for j:=0 to 3 do
    begin
    tem:=dij(i+j);
    //writeln(tem);
    //writeln(x[4],y[4]);
    if tem<min then min:=tem;
    end;
    if qh[i].c=a then begin writeln(min:0:2); halt; end;
    end;
    end.

  • 0
    @ 2014-08-03 22:24:57

    100题~

  • 0
    @ 2013-10-30 20:11:36

    DFS+A* 1A DIJSTRA神马的都麻烦爆了。。。。。
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 564 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 572 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 620 KiB, score = 20
    测试数据 #4: Accepted, time = 15 ms, mem = 700 KiB, score = 20
    Accepted, time = 15 ms, mem = 700 KiB, score = 100
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    #include <cmath>

    using namespace std;

    #define MAXN 101
    #define MAXV 500
    #define AddEdge(s,t,d) Add(s,t,d),Add(t,s,d)

    int X[MAXN][4],Y[MAXN][4],C[MAXN];
    int n,c,S,T,a,b;
    int v[MAXN][4],V=0;

    struct edge {
    edge *next;
    int t;
    double d;
    } *head[MAXN];

    void Add(int s,int t,double d) {
    edge *p=new(edge);
    p->t=t,p->next=head[s],p->d=d;
    head[s]=p;
    }

    bool check(int x1,int y1,int x2,int y2) {
    return x1*x2+y1*y2==0;
    }

    int Sqr(int x) {
    return x*x;
    }

    void INIT() {
    memset(head,0,sizeof(head));
    scanf("%d%d%d%d",&n,&c,&a,&b);
    for (int i=0;i++<n;) {
    scanf("%d%d%d%d%d%d%d",&X[i][0],&Y[i][0],&X[i][1],&Y[i][1],&X[i][2],&Y[i][2],&C[i]);
    if (check(X[i][1]-X[i][0],Y[i][1]-Y[i][0],X[i][2]-X[i][0],Y[i][2]-Y[i][0])) {
    X[i][3]=X[i][0]+X[i][1]-X[i][0]+X[i][2]-X[i][0];
    Y[i][3]=Y[i][0]+Y[i][1]-Y[i][0]+Y[i][2]-Y[i][0];
    }
    if (check(X[i][0]-X[i][1],Y[i][0]-Y[i][1],X[i][2]-X[i][1],Y[i][2]-Y[i][1])) {
    X[i][3]=X[i][1]+X[i][0]-X[i][1]+X[i][2]-X[i][1];
    Y[i][3]=Y[i][1]+Y[i][0]-Y[i][1]+Y[i][2]-Y[i][1];
    }
    if (check(X[i][1]-X[i][2],Y[i][1]-Y[i][2],X[i][0]-X[i][2],Y[i][0]-Y[i][2])) {
    X[i][3]=X[i][2]+X[i][1]-X[i][2]+X[i][0]-X[i][2];
    Y[i][3]=Y[i][2]+Y[i][1]-Y[i][2]+Y[i][0]-Y[i][2];
    }
    }
    for (int i=0;i++<n;) for (int j=0;j<4;j++) v[i][j]=++V;
    S=++V;T=++V;
    for (int i=0;i++<n;) {
    for (int j=0;j<4;j++) {
    for (int k=j+1;k<4;k++) {
    AddEdge(v[i][j],v[i][k],sqrt(Sqr(X[i][j]-X[i][k])+Sqr(Y[i][j]-Y[i][k]))*C[i]);
    }
    }
    }
    for (int i=0;i++<n;) {
    for (int j=i;j++<n;) {
    for (int k=0;k<4;k++) {
    for (int h=0;h<4;h++) {
    AddEdge(v[i][k],v[j][h],sqrt(Sqr(X[i][k]-X[j][h])+Sqr(Y[i][k]-Y[j][h]))*c);
    }
    }
    }
    }
    for (int i=0;i<4;i++) {
    AddEdge(S,v[a][i],0);
    AddEdge(v[b][i],T,0);
    }
    }

    double dist[MAXN];

    void dfs(int v) {
    for (edge *p=head[v];p;p=p->next) {
    if (dist[p->t]>dist[v]+p->d) {
    dist[p->t]=dist[v]+p->d;
    dfs(p->t);
    }
    }
    }

    int main() {
    INIT();
    for (int i=0;i++<V;) dist[i]=0x7fffffff;
    dist[S]=0;
    dfs(S);
    printf("%.2f\n",dist[T]);
    return 0;
    }

  • 0
    @ 2012-09-21 18:44:45

    题目跟原题不一样,没有询问次数n...

信息

ID
1119
难度
5
分类
图结构 | 最短路 点击显示
标签
递交数
2568
已通过
827
通过率
32%
被复制
16
上传者