第7回日本情報オリンピック 予選(オンライン)

Submission #1612011

Source codeソースコード

#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

Task問題 F - 船旅
User nameユーザ名 ecasdqina
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 820 Byte
File nameファイル名
Exec time実行時間 1466 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
set01 20 / 20 data1
set02 20 / 20 data2
set03 20 / 20 data3
set04 20 / 20 data4
set05 20 / 20 data5

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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