QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#277854 | #7883. Takeout Delivering | luhanning | RE | 0ms | 3480kb | C++17 | 1.7kb | 2023-12-07 00:04:56 | 2023-12-07 00:04:58 |
Judging History
answer
// 单源:Bellman-Ford/SPFA
// O(n*m)可以处理负权边,还能检测负环
// solution:用队列维护拓展点
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 1e3;
typedef struct edge{
int v,w; // 连接点编号,边权重
edge(int v0,int w0):v(v0),w(w0){}
bool operator >(const edge &b)const{
return w>b.w;
}
}edge;
int n; // 点数
int dist[MAXN+10];
int in[MAXN+10]; // in the queue?
vector<edge> G[MAXN+10]; // 用edge的vector保存整个图,G[i]表示以i点为起点的边的数组
void dijkstra(int p_s){ // p_s 为起点下标
for(int i=1;i<=n;i++){ // in初始化
dist[i] = 0x3f3f3f3f;
in[i] = 0;
}
dist[p_s] = 0;
for(int iii=0;iii<n;iii++){
// findmin
int minn = 0x3f3f3f3f;
int minpos = 0;
for(int i=1;i<=n;i++){
if(!in[i]&&dist[i]<minn){
minn = dist[i];
minpos = i;
}
}
if(minpos==0){
//cout<<"非连通图"<<endl;
break;
}
// 最近点入集合并更新
in[minpos] = 1;
for(int i=0;i<G[minpos].size();i++){
int v = G[minpos][i].v;
if(dist[v]>minn+G[minpos][i].w){
dist[v] = minn+G[minpos][i].w;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
int T,N; // 点数,边数。
cin>>N>>T;
n = N;
for(int i=0;i<T;i++){
int v1,v2,w;
cin>>v1>>v2>>w;
G[v1].push_back(edge(v2,w));
G[v2].push_back(edge(v1,w));
}
dijkstra(1);
cout<<dist[N]<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
input:
4 6 1 2 2 1 3 4 1 4 7 2 3 1 2 4 3 3 4 9
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: -100
Runtime Error
input:
300000 299999 80516 80517 597830404 110190 110191 82173886 218008 218009 954561262 250110 250111 942489774 66540 66541 156425292 34947 34948 239499776 273789 273790 453201232 84428 84429 439418398 98599 98600 326095035 55636 55637 355015760 158611 158612 684292473 43331 43332 43265001 171621 171622 ...