题解 - Vijos

4

伊人 LV 8 @ 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

larryzhong LV 9 @ 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

Goodhao LV 10 @ 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

孤的千年 LV 8 @ 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

Fop_zz LV 10 @ 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

fear LV 8 @ 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

天神塞勒涅 LV 10 @ 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

chronix LV 8 @ 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

Cothrax LV 8 @ 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

wang_yanheng LV 10 @ 2015-10-29 14:43:07

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

0

qq790189732 LV 8 @ 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

2859198007 LV 8 @ 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

putian9935 LV 8 @ 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

JangJingHang LV 8 @ 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

ydfq LV 10 @ 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

席一鸣 LV 8 @ 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

ws_hhh LV 8 @ 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

1036841560 LV 10 @ 2014-08-03 22:24:57

100题~

0

绿色的云 LV 10 @ 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

pr1dashuib LV 6 @ 2012-09-21 18:44:45

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

题解

98 条题解

Car的旅行路线

信息

状态

开发

支持

题解

98 条题解

Car的旅行路线

信息

状态

开发

支持

还没有账户？

登录