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
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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