hdu4360As long as Binbin loves Sangsang(多校七）（SPFA）

http://acm.hdu.edu.cn/showproblem.php?pid=4360

从昨天下午纠结到现在交了20多次。。

官方解题报告

1001

简单的图论题

每条边除了有边权以外，还有一个字母标记。标记可以是“LOVE”里面任意字符。

每个点，要拆成四个点，分别代表到达该点的标记为L,O,V,E的最短路。

第一步就是求最短路，直接spfa就可以了。

trick在于，至少要找到一个LOVE串，在只有一个节点的时候，有几条自环，至少必须走LOVE四条自环。此时，必须另外加一个节点表示开始节点。

还有一个trick就是距离可能超过int。

1 2 1314520 L

1 2 1314520 O

1 2 1314520 V

2 3 1314520 E

3 4 1314520 L

3 4 1314520 O

3 4 1314520 V

4 5 1314520 E

...

这种情况下1313个点，2624条边，每条边长度1314520，并且每条边都必须走，所以，超int了（至少signed不够）。

SPFA跑一趟就可以了。

这题将一个节点分解成四个点标记的时候也是按照一个节点分成四个标记的一个节点和字母组成一个点将满足L->O->V->E这样路线而且可以更新距离或者可以更新LOVE数目且没有被标记的那个点入队依次更新

View Code

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<string.h>
  4 #include<queue>
  5 using namespace std;
  6 #define INF 200000000000000LL
  7 struct node
  8 {
  9     int v;
 10     int w,next;
 11     char c;
 12 }men[100000];
 13 struct mode
 14 {
 15     int nu,v;
 16 };
 17 int first[2500],dd,f[100000][4],co[2500][4],a[300];
 18 __int64 s[2500][4];
 19 void init()
 20 {
 21     dd = 0;
 22     memset(first,-1,sizeof(first));
 23 }
 24 void add(int u,int v,int w,char c)
 25 {
 26     men[dd].v = v;
 27     men[dd].w = w;
 28     men[dd].c = c;
 29     men[dd].next = first[u];
 30     first[u] = dd;
 31     dd++;
 32 }
 33 void spfa(int n)
 34 {
 35     int i,j,k,m;
 36     memset(f,0,sizeof(f));
 37     memset(co,0,sizeof(co));
 38     for(i = 1; i <= n; i++)
 39     for(j = 0 ; j < 4 ; j++)
 40     s[i][j] = INF;
 41     queue<mode>q;
 42     mode mm;
 43     mm.v = 1;
 44     mm.nu = 3;
 45     co[1][3] = 0;
 46     s[1][3] = 0;
 47     f[1][3]  =1;
 48     q.push(mm);
 49     while(!q.empty())
 50     {
 51         mode kk = q.front();
 52         int nu = kk.nu;
 53         int tk = kk.v;
 54         q.pop();
 55         f[tk][nu] = 0;
 56         for(i = first[tk] ; i!=-1 ; i = men[i].next)
 57         {
 58             int v = men[i].v;
 59             int d = a[men[i].c]-1;
 60             if((nu+1)%4==d)
 61             {
 62                 if((s[v][d]>s[tk][nu]+men[i].w)||s[v][d]==0)
 63                 {
 64                     s[v][d] = s[tk][nu]+men[i].w;
 65                     co[v][d] = co[tk][nu];
 66                     if(d==3)
 67                     co[v][d]++;
 68                     if(!f[v][d])
 69                     {
 70                         f[v][d] = 1;
 71                         mm.v= v;
 72                         mm.nu = d;
 73                         q.push(mm);
 74                     }
 75                 }
 76                 else
 77                 if((s[v][d]==s[tk][nu]+men[i].w||s[v][d]==0)&&co[v][d]<=co[tk][nu])
 78                 {
 79                     co[v][d] = co[tk][nu];
 80                     if(d==3)
 81                     co[v][d]++;
 82                     if(!f[v][d])
 83                     {
 84                         f[v][d] = 1;
 85                         mm.v= v;
 86                         mm.nu = d;
 87                         q.push(mm);
 88                     }
 89                 }
 90             }
 91         }
 92     }
 93 }
 94 int main()
 95 {
 96     int i,j,k = 0,n,m,t,u,v,w;
 97     char c;
 98     a['L'] = 1;
 99     a['O'] = 2;
100     a['V'] = 3;
101     a['E'] = 4;
102     scanf("%d",&t);
103     while(t--)
104     {
105         init();
106         k++;
107         scanf("%d%d",&n,&m);
108         for(i = 1 ; i <= m ;i++)
109         {
110             scanf("%d%d%d %c",&u,&v,&w,&c);
111             add(u,v,w,c);
112             add(v,u,w,c);
113         }
114         spfa(n);
115         printf("Case %d: ",k);
116         if(co[n][3]==0||s[n][3]==INF)
117         printf("Binbin you disappoint Sangsang again, damn it!\n");
118         else
119         {
120             printf("Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n",s[n][3],co[n][3]);
121         }
122     }
123     return 0;
124 }