SRM 615 DIV1 500

TC 가 615 인 데...시간 참 빠 르 네요.
처음 500 점 을 받 았 는데 도 마음 이 설 레 었 습 니 다. 오 랜 만 에 문제 풀이, TC 홈 페이지 의 문제 풀이, 상세 하지만 영어 의... 검색 해 보 니 일본어... 알 겠 습 니 다. 영 어 를 보 겠 습 니 다.............................................
이 알고리즘 은 바로 2 차원 spfa 입 니 다. 쉽게 알 수 있 듯 이 링 mod 가 존재 합 니 다. 그러면 D + x ＊ mod = T 는 합 법 적 입 니 다.dis [d] [u] u 로 점 을 표시 할 수 있 습 니 다. 거리 모드 모드 는 d 입 니 다. 이렇게 spfa 를 뛰 면 dis [T% mod] [n - 1] < = T (T 보다 작은 것 은 mod 를 보충 할 수 있 습 니 다) 만 합 법 적 이라는 것 을 설명 할 수 있 습 니 다. 
문 제 를 보기 시 작 했 을 때 mod 가 어떻게 취 했 는 지 고민 이 많 았 는데...사실 아무 거나 mod 를 취하 면 됩 니 다. mod 는 단지 압축 을 위 한 것 입 니 다.

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <string>

 5 #include <vector>

 6 #include <queue>

 7 using namespace std;

 8 #define LL long long

 9 LL dis[20001][51];

10 int in[20001][51];

11 class LongLongTripDiv1

12 {

13     public :

14     string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T)

15     {

16         int u,v,d,mod,i;

17         mod = -1;

18         for(i = 0;i < A.size();i ++)

19         {

20             if(A[i] == 0||B[i] == 0)

21             mod = D[i];

22         }

23         if(mod == -1)

24         return "Impossible";

25         mod = mod*2;

26         memset(dis,0x7f,sizeof(dis));

27         queue< pair<int,int> > que;

28         que.push(make_pair(0,0));

29         dis[0][0] = 0;

30         in[0][0] = 1;

31         while(!que.empty())

32         {

33             pair<int,int> s = que.front();

34             d = s.first;

35             u = s.second;

36             in[d][u] = 0;

37             que.pop();

38             for(i = 0;i < A.size();i ++)

39             {

40                 if(u == A[i])

41                 v = B[i];

42                 else if(u == B[i])

43                 v = A[i];

44                 else continue;

45                 LL temp;

46                 temp = D[i] + dis[d][u];

47                 if(temp < dis[temp%mod][v])

48                 {

49                     dis[temp%mod][v] = temp;

50                     if(!in[temp%mod][v])

51                     {

52                         in[temp%mod][v] = 1;

53                         que.push(make_pair(temp%mod,v));

54                     }

55                 }

56             }

57         }

58         return dis[T%mod][N-1] <= T ? "Possible":"Impossible";

59     }

60 };