Floyd-Warshall 알고리즘 구현의 문제점

Question

INOI 2014 paper 즉 두 번째 문제를 해결하려고했습니다. FREETICKET 및 Floyd-Warshall 알고리즘을 사용하여 답을 계산했습니다. 내 코드는 최종 하위에 실패 할 나타나고 몇 가지 테스트 cases.The 코드 WA를 제공하기 위해 나타납니다 다음과

이

#include <iostream> 
#include <cstdio> 
#include <climits> 
#include <vector> 
#include <algorithm> 
using namespace std; 

typedef vector<long long int> vl; 
typedef vector<vl> vvl; 

long long int maxelem(const vvl& arr) 
{ 
    long long int max = 0, curmax; 
    for(int i = 0, l = int(arr.size());i < l;i++) 
    { 
      curmax = *(max_element(arr[i].begin(), arr[i].end())); 
      if(curmax > max) 
      { 
        max = curmax; 
      } 
    } 
    return max; 
} 

int main(void) 
{ 
    long long int c, f, x, y, p; 
    scanf("%lld%lld", &c, &f); 
    vvl adj(c, vl(c, 26336)); 
    for(int i = 0;i < f;i++) 
    { 
     scanf("%lld%lld%lld", &x, &y, &p); 
     adj[x-1][y-1] = p; 
     adj[y-1][x-1] = p;   
    } 
    long long int max = 0; 
    for(int k = 0;k < c;k++) 
    { 
      for(int i = 0;i < c;i++) 
      { 
        for(int j = 0;j < i;j++) 
        { 
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);   
        } 
        for(int j = (i + 1);j < c;j++) 
        { 
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);   
        }  
      } 
    } 
    max = maxelem(adj); 
    printf("%lld\n", max); 
} 

이 코드는 단지 인접 행렬을 사용하고 사람에서 이동하지 않도록합니다 동일한 장소, 동일한 장소 (가장 안쪽 루프에서). 하위 작업 3에서 하위 작업 중 일부를 수행하지 못하면 50/100 점이 표시됩니다. 누군가 내 코드에서 버그를 찾는 것을 도울 수 있습니까? 심지어 long long int의 데이터 형식을 변경하려고 시도했습니다. (그냥 안전하기 위해).

은 너 한테의 문제는

Answer 1

입니다 :

for(int i = 0;i < f;i++) 
{ 
     scanf("%lld%lld%lld", &x, &y, &p); 
     adj[x-1][y-1] = p; 
     adj[y-1][x-1] = p;   
} 

그것은해야한다 : 도시 a를 사이에 여러 개의 경로가있는 경우

for(int i = 0;i < f;i++) 
{ 
     scanf("%lld%lld%lld", &x, &y, &p); 
     adj[x-1][y-1] = min(p, adj[x-1][y-1]); 
     adj[y-1][x-1] = min(p, adj[y-1][x-1]);   
} 

가 있기 때문에 -> b는, 우리가 가장 저렴한를 취할 필요 노선.

그리고 당신은 모든 0 <= i < c