题解 - Vijos

2

【题解】求次短路，dijkstra第一遍的时候记录边，然后按照记录的边返回进行删边操作。

#include<cstdio>
#include<cmath>
#include<queue>
#include<utility>
#include<vector>
#include<cstring>
using namespace std;
#define INF 1e9
const int maxn=210,maxm=50000;
struct Edge{
    int to,next;
    double dist;
}edges[maxm];
int head[maxn]={0},size=0,x[maxn],y[maxn];
int n,m;
double dst(int x1,int y1,int x2,int y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double min(double a,double b){
    return a>b?b:a;
}
void AddEdge(int from,int to,double dist){
    size++;
    edges[size].to=to,edges[size].dist=dist;
    edges[size].next=head[from];
    head[from]=size;
}
typedef pair<double,int> pii;
double d[maxn],ans=INF;
int Prev[maxn];//p大写，否则与默认函数冲突 
void dijkstra(int a,int b){//删除a与b之间的路 
    bool done[maxn]={0};
    for(int i=1;i<=n;i++)d[i]=INF;
    d[1]=0;
    priority_queue<pii,vector<pii>,greater<pii> >Q;
    Q.push(pii(0,1));
    while(!Q.empty()){
        int u=Q.top().second;
        double w=Q.top().first;
        Q.pop();
        if(done[u])continue;
        done[u]=true;
        for(int i=head[u];i;i=edges[i].next){
            Edge &e=edges[i];
            if(u==a&&e.to==b||u==b&&e.to==a)continue;//是个无向图 
            if(d[e.to]>w+e.dist){
                if(a==-1&&b==-1)Prev[e.to]=u;//在删边的时候不能记录 
                d[e.to]=w+e.dist;
                Q.push(pii(d[e.to],e.to));
            }
        }
    }
}
int main()
{
    int from,to;
    double dist=0.0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&from,&to);
        dist=dst(x[from],y[from],x[to],y[to]);
        AddEdge(from,to,dist);AddEdge(to,from,dist);
    }
    dijkstra(-1,-1);
    int now=n;
    while(Prev[now]){//删边过程 
        dijkstra(Prev[now],now);
        ans=min(d[n],ans);
        now=Prev[now];
    }
    if(ans==INF)printf("-1\n");
    else printf("%.2lf",ans);
    return 0;
 }

0

PowderHan LV 10 @ 7 年前

/*
先求一次最短路，记录下路径。
再不断删除一条最短路上的路线，求出此时的距离，取其最小值。
即删边法>3<
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <queue>
#include <cmath>
using namespace std;

const double INF=666666.0;
struct node
{
    double x,y;
}a[203];
double dist[203];
double d[203];
double map[203][203];
int fa[203];
bool in[203];
int n,m;
double min1,min2;
queue<int> q;

double turn(int x,int y)
{
    double dx=a[x].x-a[y].x;
    double dy=a[x].y-a[y].y;
    double r=dx*dx+dy*dy;
    return sqrt(r);
}

void init()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            map[i][j]=INF;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        map[x][y]=map[y][x]=turn(x,y);
    }

}

void SPFA(int s)
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=0;
        dist[i]=INF;
        in[i]=false;
    }
    while(!q.empty())
        q.pop();
    q.push(s);
    in[s]=true;
    dist[s]=0;

    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        in[x]=false;

        for(int i=1;i<=n;i++)
            if(dist[i]>dist[x]+map[x][i])
            {
                dist[i]=dist[x]+map[x][i];
                fa[i]=x;
                if(!in[i])
                {
                    in[i]=1;
                    q.push(i);
                }
            }
    }
}

void spfa(int s)//两次的SPFA不同，即不需要记录最短路径
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
    memset(in,0,sizeof(in));
    q.push(s);
    in[s]=1;
    d[s]=0;

    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        in[x]=0;

        for(int i=1;i<=n;i++)
        {
            if(d[i]>d[x]+map[x][i])
            {
                d[i]=d[x]+map[x][i];
                if(!in[i])
                {
                    in[i]=1;
                    q.push(i);
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    init();
    //先求出最短路，fa[]记录
    SPFA(1);
    min1=dist[n];
    int now=n;
    int p1,p2;
    min2=INF;
    while(fa[now])
    {
        //沿着最短路一路返回
        p1=now;
        p2=fa[now];
        now=fa[now];
        //记录下值以便还原边
        double t=map[p1][p2];
        //删除边
        map[p1][p2]=map[p2][p1]=INF;
        //求删边后的最短路
        spfa(1);
        //记录删边后的所有路最短路中的最小距离值
        min2=min(min2,d[n]);
        //还原边
        map[p1][p2]=map[p2][p1]=t;
    }
    if(min2==INF)
        cout<<-1<<endl;
    else 
        printf("%.2lf\n",min2);
    return 0;
}

0

1464942666 LV 8 @ 8 年前

First of all, 我只能说无语了。标准的次短路程序居然不能AC。觉得题目应该有问题，因为是*无向图*，所以存在***最短路***就一定存在***次短路***（大不了***绕个环***嘛），结果就只能这样了

编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 1936 KiB, score = 10
测试数据 #1: WrongAnswer, time = 15 ms, mem = 1936 KiB, score = 0
测试数据 #2: Accepted, time = 0 ms, mem = 1940 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1960 KiB, score = 10
测试数据 #4: WrongAnswer, time = 0 ms, mem = 1980 KiB, score = 0
测试数据 #5: Accepted, time = 0 ms, mem = 1976 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1976 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1976 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1976 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1976 KiB, score = 10
WrongAnswer, time = 45 ms, mem = 1980 KiB, score = 80

80分的代码在此：
(想学次短路的人抱歉，没有写注释，但是这里安利一篇博客，想看就看吧)
［http://blog.csdn.net/kalilili/article/details/43450537］
#Block Code
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <utility>
#include <functional>
using namespace std;
#define xinstream
const int MaxV = 210, Inf = 1 << 29;
#define d(x,y) dist[x][y]
typedef pair<double, int> pdi;
struct _edge {
int to, next;
double weit;
_edge() {to = next = -1; weit = 0;}
} edges[MaxV * MaxV << 1];

int numE, numV, idx;
int xx[MaxV], yy[MaxV], head[MaxV];
double dist[MaxV][2];
priority_queue<pdi, vector<pdi>, greater<pdi> > q;

inline bool equ(double a, double b) {
a -= b;
// printf("%lf\n", a);
return a > -0.0000001 && a < 0.0000001;
}
inline int sqr(int x) {
return x * x;
}

inline void dijkstra(int sors) {
while (!q.empty()) q.pop();
for (int i = 0; i <= numV; i++) dist[i][0] = dist[i][1] = Inf;
dist[sors][0] = dist[sors][1] = 0;
q.push(make_pair(0, sors));
while (!q.empty()) {
pdi x = q.top(); q.pop();
int u = x.second; double dd = x.first;
if (x.first > dist[u][1]) continue;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to; dd = x.first + edges[i].weit;
if (d(v, 0) > dd) { //|| equ(d(v, 0), x.first + w)
swap(d(v, 0), dd);
q.push(make_pair(dist[v][0], v));
}
if (dist[v][1] > dd) {
dist[v][1] = dd;
q.push(make_pair(dist[v][1], v));
}
}
}
}

inline void addEdge(int u, int v, double w) {
if (equ(w, 0)) return;
_edge &e = edges[idx];
e.to = v; e.weit = w; e.next = head[u];
head[u] = idx++;
}

inline void init() {
int u, v; double w;
scanf("%d%d", &numV, &numE);
idx = 0; memset(head, -1, sizeof(head));
for (int i = 1; i <= numV; i++) scanf("%d%d", &xx[i], &yy[i]);
for (int i = 0; i < numE; i++) {
scanf("%d%d", &u, &v);
w = sqrt(sqr(xx[u] - xx[v]) + sqr(yy[u] - yy[v]));
addEdge(u, v, w); addEdge(v, u, w);
}
}

int main() {
#ifdef instream
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);

init();
dijkstra(1);
if (d(numV, 1) != Inf)
printf("%.2lf\n", d(numV, 1));
else
printf("-1\n");
return 0;
}

So，标程也应该是拿删边来做的，数据也是用删边的方法出的。但是显然我们可以***构造一组数据***让删边的做法**WA**，有兴趣就自己想想。
Then, 想AC的话就用一下楼下*@chronix* 的代码吧。

0

chronix LV 8 @ 8 年前

我只能说**坑爹**
%.2f是 四舍五入 我还傻乎乎的加0.005
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 724 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 724 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 724 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 728 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 724 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 728 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 728 KiB, score = 10
Accepted, time = 30 ms, mem = 728 KiB, score = 100
代码
```c++
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>

//#define debug

using std::queue;

float INF=666666.0;

int n,m;
float x[210],y[210];
float map[210][210];
float min1st;

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

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

void read(int s,int d,float v) {
map[s][d]=v;
map[d][s]=v;
}

void build() {
init();
scanf("%d%d",&n,&m);
int s,d;
float v;
for(int i=1; i<=n; i++) {
scanf("%f%f",&x[i],&y[i]);//zuo biao
}

int x1,y1,x2,y2;

for(int i=1; i<=m; i++) {
scanf("%d%d",&s,&d);
x1=x[s];
y1=y[s];
x2=x[d];
y2=y[d];
v=calc(x1,y1,x2,y2);//calc juli
read(s,d,v);
}
}

//SPFA1

int inque[210]= {0};
float dist[210];
int father[210];
queue <int> q;

void spfa1(int s) { //每次重载：father,dist,inque,q,
for(int i=0; i<=205; i++){
father[i]=0;
dist[i]=INF;
inque[i]=0;
if(!q.empty())
q.pop();
}

q.push(s);
inque[s]=1;
dist[s]=0;
int t;
while(!q.empty()) {
t=q.front();
q.pop();
inque[t]=0;

for(int i=1; i<=n; i++) {
float v=map[t][i];
if(v!=INF) {

if(dist[t]+v<dist[i]) {
dist[i]=dist[t]+v;
father[i]=t; //-----path
// dist[next]>dist[now]+value)
if(!inque[i]) {
q.push(i);
inque[i]=1;
}
}
}
}
}
}

float dist2[210];

/*
思路：首先一遍spfa 找出最短路记录路径
然后依次删边：father【】不更新 dist2更新

*/
void spfa2(int s) {

for(int i=0; i<=205; i++){
dist2[i]=INF;
inque[i]=0;
if(!q.empty())
q.pop();
}

for(int i=1; i<=n; i++)
dist2[i]=INF;
q.push(s);
inque[s]=1;
dist2[s]=0;
int t;
while(!q.empty()) {
t=q.front();
q.pop();
inque[t]=0;
for(int i=1; i<=n; i++) {
float v=map[t][i];
if(v!=INF) {

if(dist2[t]+v<dist2[i]) {
dist2[i]=dist2[t]+v;

// dist[next]>dist[now]+value)
if(!inque[i]) {
q.push(i);
inque[i]=1;
}
}
}
}
}
}

int main() {

#ifdef debug
freopen("in.txt","r",stdin);
#endif

build();

spfa1(1);
min1st=dist[n];//1st最短路
//寻找路径：
int now=n;
float temp;
int p1,p2;
float min2nd=INF;
while(father[now]){
p1=now;
p2=father[now];
// if(p1==p2)
// break;
now=father[now];
//封路 :
temp=map[p1][p2];//recover
map[p1][p2]=INF;
map[p2][p1]=INF;
//重新计算:
spfa2(1);

if(min2nd>dist2[n])
min2nd=dist2[n];
//recover:
map[p1][p2]=temp;
map[p2][p1]=temp;
}

if(INF==min2nd){
printf("-1");
return 0;
}

printf("%.2f",min2nd);

return 0;
}
```

0

chronix LV 8 @ 9 年前

为什么只过两个点？？？？？？
各位大神求解!
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>

//#define debug

using std::queue;

float INF=666666.0;

int n,m;
float x[210],y[210];
float map[210][210];
float min1st;

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

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

void read(int s,int d,float v) {
map[s][d]=v;
map[d][s]=v;
}

void build() {
init();
scanf("%d%d",&n,&m);
int s,d;
float v;
for(int i=1; i<=n; i++) {
scanf("%f%f",&x[i],&y[i]);//zuo biao
}

int x1,y1,x2,y2;

for(int i=1; i<=m; i++) {
scanf("%d%d",&s,&d);
x1=x[s];
y1=y[s];
x2=x[d];
y2=y[d];
v=calc(x1,y1,x2,y2);//calc juli
read(s,d,v);
}
}

//SPFA1

int inque[210]= {0};
float dist[210];
int father[210];
queue <int> q;

void spfa1(int s) {
for(int i=1; i<=n; i++)
dist[i]=INF;
memset(father,0,sizeof(father));
q.push(s);
inque[s]=1;
dist[s]=0;
int t;
while(!q.empty()) {
t=q.front();
q.pop();
inque[t]=0;

for(int i=1; i<=n; i++) {
float v=map[t][i];
if(v!=INF) {

if(dist[t]+v<dist[i]) {
dist[i]=dist[t]+v;
father[i]=t; //-----path
// dist[next]>dist[now]+value)
if(!inque[i]) {
q.push(i);
inque[i]=1;
}
}
}
}
}
}

float dist2[210];

void spfa2(int s) {
for(int i=1; i<=n; i++)
dist2[i]=INF;
q.push(s);
inque[s]=1;
dist2[s]=0;
int t;
while(!q.empty()) {
t=q.front();
q.pop();
inque[t]=0;
for(int i=1; i<=n; i++) {
float v=map[t][i];
if(v!=INF) {

if(dist2[t]+v<dist2[i]) {
dist2[i]=dist2[t]+v;

// dist[next]>dist[now]+value)
if(!inque[i]) {
q.push(i);
inque[i]=1;
}
}
}
}
}
}

int main() {

#ifdef debug
freopen("in.txt","r",stdin);
#endif

build();

spfa1(1);
min1st=dist[n];//1st最短路
//寻找路径：
int now=n;
float temp;
int p1,p2;
float min2nd=INF;
while(father[now]){
p1=now;
p2=father[now];
if(p1==p2)
continue;
now=father[now];
//封路 :
temp=map[p1][p2];//recover
map[p1][p2]=INF;
map[p2][p1]=INF;
//重新计算:
spfa2(1);

if(min2nd>dist2[n])
min2nd=dist2[n];
//recover:
map[p1][p2]=temp;
map[p2][p1]=temp;
}

if(INF==min2nd){
printf("-1");
return 0;
}

printf("%.2f",min2nd+0.005);

return 0;
}

0

xxxxxxxxyu LV 8 @ 9 年前

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<iostream>
#include<string>
#include<cmath>
using namespace std;

typedef double ll;
int n,m;
struct point
{

int x;
double y;
point(int x=0,double y=0):x(x),y(y){}
};
struct edge
{
ll x, y;
}edge[10000];
double yu[205][205];
int vis[202];
double number1=1000000;
double number2=1000000;
int number22=1;
vector<int>q[205];
double mins(double x,double y)
{
if(x<=y)return x;
else return y;

}
void ans()
{
memset(vis,0,sizeof(vis));
queue<point>d;
point a(1,0);
d.push(a);
point end_point(n);
while(!d.empty())
{
point u=d.front();
d.pop();
int x=u.x;
double y=u.y;
if(x==end_point.x){
if(y==number1)number22++;
if(y<number1)number22=1;
number1=mins(y,number1);

if(y>number1&&y<number2)number2=y;

}
else if(!vis[x]){
for(int i=0;i<q[x].size();i++)
{
if(y+yu[x][q[x][i]]<number2){d.push(point(q[x][i],y+yu[x][q[x][i]]));}
}
vis[x]=1;}

}

}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>edge[i].x>>edge[i].y;
}
for(int i=1;i<=m;i++)
{
int o,p;
cin>>o>>p;
yu[o][p]=sqrt((edge[o].x-edge[p].x)*(edge[o].x-edge[p].x)+(edge[o].y-edge[p].y)*(edge[o].y-edge[p].y));
q[o].push_back(p);
q[p].push_back(o);
yu[p][o]=yu[o][p];
}
ans();
if(number22>1)printf("%.2f",number1);
else if(number2!=1000000){printf("%.2f",number2);}
else{cout<<"-1";}
return 0;
}

为什么只对了两组

0

nzhtl1477 LV 10 @ 9 年前

P1155集合位置
Accepted

记录信息

评测状态 Accepted
题目 P1155 集合位置
递交时间 2015-07-03 11:28:44
代码语言 C++
评测机 VijosEx
消耗时间 82 ms
消耗内存 520 KiB
评测时间 2015-07-03 11:28:45

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 520 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 520 KiB, score = 10

测试数据 #2: Accepted, time = 7 ms, mem = 520 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 516 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 520 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 520 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 520 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 520 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 516 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 520 KiB, score = 10

Accepted, time = 82 ms, mem = 520 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>

using namespace std;

int n , m;
float a[200 + 2][200 + 2];
float posx[200 + 2] , posy[200 + 2];
float dist[200 + 2];
int pre[200 + 2];
int p[200 + 2];
int use[200 + 2];
queue < int > q;
int present;

int i , j , k;
int x , y;
float ans;
float now;
float maxd;

struct link
{
int x , y;
};

link l[10000 + 2];

int getpath( int x )
{
if( pre[x] == -1 )
return x;
p[i++] = x;
return getpath( pre[x] );
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
scanf( "%f %f" , &posx[i] , &posy[i] );
for( i = 1 ; i <= n ; i++ )
pre[i] = -1;
for( i = 1 ; i <= n ; i++ )
dist[i] = 1000000;
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= n ; j++ )
a[i][j] = 1000000;
dist[1] = 0;
for( i = 0 ; i < m ; i++ )
{
scanf( "%d %d" , &x , &y );
a[x][y] = a[y][x] = sqrt( ( posx[x] - posx[y] ) * ( posx[x] - posx[y] ) + ( posy[x] - posy[y] ) * ( posy[x] - posy[y] ) );
}
q.push( 1 );
while( !q.empty() )
{
present = q.front();
q.pop();
use[present] = 0;
for( i = 1 ; i <= n ; i++ )
if( dist[i] > dist[present] + a[present][i] )
{
pre[i] = present;
dist[i] = dist[present] + a[present][i];
if( !use[i] )
{
q.push( i );
use[i] = 1;
}
}
}
i = 0;
getpath( n );
for( i = 0 ; p[i] != 0 ; i++ )
;
p[i] = 1;
for( i = 0 ; i < n - 1 && p[i + 1] != 0 ; i++ )
{
l[i].x = p[i];
l[i].y = p[i + 1];
}
if( dist[n] == 1000000 )
{
cout << -1 << endl;
return 0;
}
maxd = 1000000;
for( i = 0 ; i < n - 1 && p[i + 1] != 0 ; i++ )
{
for( j = 1 ; j <= n ; j++ )
dist[j] = 1000000;
dist[1] = 0;
x = l[i].x;
y = l[i].y;
now = a[x][y];
a[x][y] = a[y][x] = 1000000;
q.push( 1 );
memset( use , 0 , sizeof( use ) );
while( !q.empty() )
{
present = q.front();
q.pop();
use[present] = 0;
for( j = 1 ; j <= n ; j++ )
{
if( dist[j] > dist[present] + a[present][j] )
{
dist[j] = dist[present] + a[present][j];
if( !use[j] )
{
use[j] = 1;
q.push( j );
}
}
}
}
maxd = min( maxd , dist[n] );
a[x][y] = a[y][x] = now;
}
printf( "%.2f\n" , maxd );
//system( "pause" );
return 0;
}

0

孖作多情、 LV 9 @ 11 年前

求救，第三个点是什么

0

神犇 LV 10 @ 12 年前

***|\**|\**|\**|\*|*毛线啊同样的程序连交5次每次都超时而且不是超时就是0MS 最**|的是超时的点居然不同！第五次AC。。。0MS。。。卧槽

0

cczzbb456 LV 8 @ 14 年前

题目里加上一个要求：不能走重复路！要不就必须搜索了。

0

xiaoqian LV 8 @ 15 年前

great!

第一次写次短路，一次AC!

0

zhh1993 LV 10 @ 15 年前

Accepted 有效得分：100 有效耗时：0ms

太高兴了，第一次找次短路就AC了~~其实就和次小生成树的方法一样~~

一遍spfa找到最短路，然后逐条删边再用spfa去找题目要求的次短路……

0

prince_hao LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

最近手好顺啊

整天的1A~

0

mintalfance LV 10 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

spfa

0

Nerazzurri LV 8 @ 15 年前

const maxedge=40000;

maxsize=200;

maxqueue=100000;

type pathtype=record

s,t:longint;

end;

var g:array[1..maxsize,1..maxsize] of double;

dist:array[1..maxsize] of double;

from,x,y:array[1..maxsize] of longint;

hash:array[1..maxsize] of boolean;

queue:array[1..maxqueue] of longint;

path:array[1..maxedge] of pathtype;

n,count:longint;

procedure pretreatment;

var i,j,m,s,t:longint;

begin

readln(n,m);

for i:=1 to n do

read(x[i],y[i]);

for i:=1 to n do

for j:=1 to n do

g:=maxlongint shr 2;

for i:=1 to m do

begin

read(s,t);

g:=sqrt((x-x[t])*(x-x[t])+(y-y[t])*(y-y[t]));

g[t,s]:=sqrt((x-x[t])*(x-x[t])+(y-y[t])*(y-y[t]));

end;

end;

procedure find_shortest;

var i,p1,p2:longint;

begin

for i:=1 to n do dist[i]:=maxlongint shr 2;

dist[1]:=0;

fillchar(hash,sizeof(hash),false);

fillchar(from,sizeof(from),0);

p1:=1;p2:=1;

queue[1]:=1;

hash[1]:=true;

while p1g[queue[p1],i]+dist[queue[p1]] then

begin

dist[i]:=g[queue[p1],i]+dist[queue[p1]];

from[i]:=queue[p1];

if not hash[i] then

begin

hash[i]:=true;

inc(p2);

queue[p2]:=i;

end;

end;

hash[queue[p1]]:=false;

inc(p1);

end;

end;

procedure save_path;

var now:longint;

begin

count:=0;

now:=n;

while from[now]0 do

begin

inc(count);

path[count].s:=now;

path[count].t:=from[now];

now:=from[now];

end;

end;

procedure solve;

var i:longint;

ans:double;

begin

ans:=maxlongint shr 2;

for i:=1 to count do

begin

g[path[i].s,path[i].t]:=maxlongint shr 2;

g[path[i].t,path[i].s]:=maxlongint shr 2;

find_shortest;

if dist[n]

0

nlogn LV 8 @ 15 年前

我想知道我没有输出-1的情况，为啥ac了。。。

我用了一个明显错误的Floyd，为啥也ac了。。。

0

尖端才子 LV 10 @ 15 年前

我在想……为啥非得删边呢？不能记录前两优的解吗？然后updata一撮数据？标准的第k短路啊……时间复杂度应该是O（N^2k）的……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出 659....

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出 595....

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出 213.7...

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：70 有效耗时：0ms

正在怀疑数据ing……这个……我是standard啊……怎么可能错呢？

SPFA*O(k)=70……

囧了……难道真得删边？那样就是O（N^3-N^2）……

或者来个DP的FLoyed？。。。一切还都未知，我写写看吧……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这是删边后的结果……。。。我无语。。。

0

K-Boy LV 10 @ 15 年前

其实......N次DIJ才是王道..........

先用DIJ求最短路，然后记录在更新过程中的每个‘使F[1,j]更新’的点为G[j]

则(G[j],j)即为一条最短路上的边

然后由G[n]倒推回去，找出在1---|->N最短路上的边

之后枚举每个边删去，

进行DIJ，

如果不是等于已经求出的最小值就更新

0

xjc9909 LV 7 @ 15 年前

第三个点怎么回事啊，floyd和dj都过不了

0

laz LV 10 @ 15 年前

变量打错=60分囧rz、、、

终于给AC了=。=

题解

59 条题解

集合位置

信息

状态

开发

支持

题解

59 条题解

集合位置

信息

状态

开发

支持

还没有账户？

登录