题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4360
思路：首先就是要寻找最短路了，然后就是要着“LOVE”连着最多的最短路了，这里我们可以用一个二维数组来记录“LOVE”最多的最短路，然后每次spfa更新的时候维护一下就可以了（每当以‘E'结尾是就要num[i][j]++),最后的情况就是要考虑一下特判n==1是的情况了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<vector> 7 using namespace std; 8 #define MAXN 2222 9 typedef long long LL; 10 #define inf (1ll)<<61 11 typedef pair<int,int>Pair; 12 struct Node{ 13 int v,w,id; 14 }; 15 LL dist[MAXN][4]; 16 int num[MAXN][4]; 17 bool mark[MAXN][4]; 18 int n,m; 19 char str[4]; 20 vector<Node>map[MAXN]; 21 22 int Change(char ch){ 23 if(ch=='L')return 0; 24 else if(ch=='O')return 1; 25 else if(ch=='V')return 2; 26 else if(ch=='E')return 3; 27 } 28 29 void spfa(){ 30 for(int i=0;i<=n;i++) 31 for(int j=0;j<4;j++) 32 dist[i][j]=inf; 33 memset(mark,false,sizeof(mark)); 34 memset(num,0,sizeof(num)); 35 dist[1][3]=0; 36 mark[1][3]=true; 37 queue<Pair>Q; 38 Q.push(make_pair(1,3)); 39 while(!Q.empty()){ 40 Pair pp=Q.front(); 41 Q.pop(); 42 int u=pp.first; 43 int id=pp.second; 44 mark[u][id]=false; 45 // printf("%d\n",id); 46 for(int i=0;i<map[u].size();i++){ 47 int v=map[u][i].v; 48 int w=map[u][i].w; 49 int nid=map[u][i].id; 50 if((id+1)%4==nid){ 51 if(dist[v][nid]>dist[u][id]+w){ 52 dist[v][nid]=dist[u][id]+w; 53 num[v][nid]=num[u][id]; 54 if(nid==3)num[v][nid]++; 55 if(!mark[v][nid]){ mark[v][nid]=true;Q.push(make_pair(v,nid)); } 56 }else if(dist[v][nid]==dist[u][id]+w&&num[v][nid]<=num[u][id]){ 57 num[v][nid]=num[u][id]; 58 if(nid==3)num[v][nid]++; 59 if(!mark[v][nid]){ mark[v][nid]=true;Q.push(make_pair(v,nid)); } 60 } 61 } 62 } 63 //特判 64 if(n==1&&num[1][3]==0&&dist[1][3]==0) 65 dist[1][3]=inf; 66 } 67 } 68 69 70 int main(){ 71 int _case,t=1,u,v,w,tmp; 72 scanf("%d",&_case); 73 while(_case--){ 74 scanf("%d%d",&n,&m); 75 for(int i=1;i<=n;i++)map[i].clear(); 76 for(int i=1;i<=m;i++){ 77 scanf("%d%d%d%s",&u,&v,&w,str); 78 tmp=Change(str[0]); 79 Node p1,p2; 80 p1.v=v,p2.v=u; 81 p1.w=p2.w=w; 82 p1.id=p2.id=tmp; 83 map[u].push_back(p1); 84 map[v].push_back(p2); 85 } 86 spfa(); 87 if(dist[n][3]==inf||num[n][3]==0){ 88 printf("Case %d: Binbin you disappoint Sangsang again, damn it!\n",t++); 89 }else 90 printf("Case %d: Cute Sangsang, Binbin will come with a donkey after travelling %I64d meters and finding %d LOVE strings at last.\n",t++,dist[n][3],num[n][3]); 91 } 92 return 0; 93 }