CSES - Datatähti 2020 alku - Results
Submission details
Task:Mastot
Sender:ph
Submission time:2019-10-13 22:56:20 +0300
Language:C++11
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:80:28: error: invalid conversion from 'long int (*)[200001]' to 'long int' [-fpermissive]
  long graph = new long[V][V];
                            ^
input/code.cpp:101:11: error: invalid types 'long int[int]' for array subscript
    graph[i][j] = c[j];
           ^
input/code.cpp:112:22: error: invalid conversion from 'long int' to 'long long int (*)[200001]' [-fpermissive]
  dijkstra(graph, 0, n);
                      ^
input/code.cpp:24:6: note:   initializing argument 1 of 'void dijkstra(long long int (*)[200001], int, int)'
 void dijkstra(long long graph[V][V], int src, int dest) 
      ^~~~~~~~

Code

#include<bits/stdc++.h>
using namespace std;
#define V 200001

long long minDistance(long long dist[], bool sptSet[]) 
{ 
    // Initialize min value 
    long long min = LLONG_MAX, min_index; 
  
    for (int v = 0; v < V; v++) 
        if (sptSet[v] == false && dist[v] <= min) 
            min = dist[v], min_index = v; 
  
    return min_index; 
} 

void printSolution(int dist[]) 
{ 
    printf("Vertex \t\t Distance from Source\n"); 
    for (int i = 0; i < V; i++) 
        printf("%d \t\t %d\n", i, dist[i]); 
} 

void dijkstra(long long graph[V][V], int src, int dest) 
{ 
    long long dist[V]; // The output array.  dist[i] will hold the shortest 
    // distance from src to i 
  
    bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest 
    // path tree or shortest distance from src to i is finalized 
  
    // Initialize all distances as INFINITE and stpSet[] as false 
    for (int i = 0; i < V; i++) 
        dist[i] = LLONG_MAX, sptSet[i] = false; 
  
    // Distance of source vertex from itself is always 0 
    dist[src] = 0; 
  
    // Find shortest path for all vertices 
    for (int count = 0; count < V - 1; count++) { 
        // Pick the minimum distance vertex from the set of vertices not 
        // yet processed. u is always equal to src in the first iteration. 
        long long u = minDistance(dist, sptSet); 
  
        // Mark the picked vertex as processed 
        sptSet[u] = true; 
  
        // Update dist value of the adjacent vertices of the picked vertex. 
        for (int v = 0; v < V; v++) 
  
            // Update dist[v] only if is not in sptSet, there is an edge from 
            // u to v, and total weight of path from src to  v through u is 
            // smaller than current value of dist[v] 
            if (!sptSet[v] && graph[u][v] && dist[u] != LLONG_MAX
                && dist[u] + graph[u][v] < dist[v]) 
                dist[v] = dist[u] + graph[u][v]; 
    } 
  
    // print the constructed distance array 
    cout << dist[dest]-1;
} 

int main() {
	// ios_base::sync_with_stdio(true);
	// cin.tie(NULL);
	int n;
	// string line;
	// getline(cin, line);
	// stringstream split_n(line);
	// split_n >> n;
	// getline(cin, line);
	// stringstream split_d(line);
	// getline(cin, line);
	// stringstream split_c(line);
	// ifstream in("dt_4_test.txt");
	// in >> n;
	cin >> n;
	int d[n];
	int c[n];
	long graph = new long[V][V];
	for (int i = 0; i < n; i++) {
		cin >> d[i];
		// in >> d[i];
	}
	
	for (int i = 1; i < n; i++) {
		cin >> c[i];
		// in >> c[i];
	}
	
	// split_d >> d[0];
	// for (int i = 1; i < n; i++) {
		// split_d >> d[i];
		// split_c >> c[i];
	// }
	d[n] = 0;
	c[n] = 1;
	
	for (int i = 0; i <= n; i++) {
		for (int j = i+1; j <= min(i+d[i],n); j++) {
			graph[i][j] = c[j];
		}
	}
	
	// for (int i = 0; i <= n; i++) {
		// for (int j = 0; j <= n; j++) {
			// cout << graph[i][j] << " ";
		// }
		// cout << endl;
	// }
	
	dijkstra(graph, 0, n);
}