思路:
翻译题…翻译题…难道是我校被Q了吗?正权无向稠密图,求源点到所有点的最短路,输出最长一条的长度。使用:Dijkstra,邻接矩阵,atoi函数。
代码:
0ms 748kB
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 105;
int N
;
int mp
[maxn
][maxn
];
int dis
[maxn
];
struct NODE
{
int id
;
int dis
;
friend bool operator
> (NODE a
, NODE b
){
return a
.dis
> b
.dis
;
}
NODE(int id
,int dis
) : id(id
) , dis(dis
) {} ;
};
priority_queue
<NODE
, vector
<NODE
> , greater
<NODE
> > Q
;
bool vis
[maxn
];
int ans
= 0;
void IJK(){
memset(vis
,0,sizeof(vis
));
memset(dis
,INF
,sizeof(dis
));
Q
.push(NODE(1,0));dis
[1]=0;
while(Q
.size()){
NODE cur
= Q
.top() ; Q
.pop() ;
if(vis
[cur
.id
])
continue;
vis
[cur
.id
] = true
;
for(int i
=1;i
<=N
;i
++){
if(vis
[i
])
continue;
if(dis
[i
] > dis
[cur
.id
] + mp
[cur
.id
][i
]){
dis
[i
] = dis
[cur
.id
] + mp
[cur
.id
][i
];
Q
.push(NODE(i
,dis
[i
]));
}
}
}
for(int i
=1;i
<=N
;i
++)
if(dis
[i
] == INF
)
continue;
else
ans
= max(ans
, dis
[i
]);
return ;
}
int main(){
cin
>>N
;
for(int i
=2;i
<=N
;i
++){
for(int j
=1;j
<=i
-1;j
++){
char str
[30];
scanf("%s",str
);
if(str
[0] == 'x')
mp
[i
][j
] = mp
[j
][i
] = INF
;
else
mp
[i
][j
] = mp
[j
][i
] = atoi(str
);
}
}
for(int i
=1;i
<=N
;i
++)
mp
[i
][i
] = 0;
IJK();
cout
<<ans
<<endl
;
return 0;
}
转载请注明原文地址: https://yun.8miu.com/read-55403.html