Submission #1612011
Source Code Expand
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7;
const int MAX_N=10000;
int n,k,a,b,c,li[101][101]={},dp[101];
int main(){
cin >> n >> k;
REP(i,0,k){
cin >> a;
if(a){
cin >> a >> b >> c;
if(li[a][b]){
li[a][b]=min(li[a][b],c);
li[b][a]=min(li[b][a],c);
}else{
li[a][b]=c;
li[b][a]=c;
}
}else{
cin >> a >> b;
fill(dp,dp+sizeof(dp)/sizeof(dp[0]),INF);
dp[a]=0;
REP(k,0,20){
REP(i,0,n+1){
REP(j,0,n+1){
if(li[i][j]){
dp[j]=min(dp[j], dp[i]+li[i][j]);
}
}
}
}
cout << (dp[b]!=INF?dp[b]:-1) << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - 船旅 |
User |
ecasdqina |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
820 Byte |
Status |
AC |
Exec Time |
1466 ms |
Memory |
256 KB |
Judge Result
Set Name |
set01 |
set02 |
set03 |
set04 |
set05 |
Score / Max Score |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
Status |
|
|
|
|
|
Set Name |
Test Cases |
set01 |
data1 |
set02 |
data2 |
set03 |
data3 |
set04 |
data4 |
set05 |
data5 |
Case Name |
Status |
Exec Time |
Memory |
data1 |
AC |
1 ms |
256 KB |
data2 |
AC |
3 ms |
256 KB |
data3 |
AC |
61 ms |
256 KB |
data4 |
AC |
593 ms |
256 KB |
data5 |
AC |
1466 ms |
256 KB |