题意：求出一个图的最短路的数量，并求出在最短路的条件下求出获得权值最大的路。
我的做法就是用优先队列优化Dijkstra算法，就是在mindis[v]>mindis[number]+dis[i]（i是边的编号，v是边的终点，number是边的始点），或者在mindis[v]==mindis[number]+dis[i]的条件下maxcost[v]<num[v]+maxcost[number]就需要松弛。
但是由于对优先队列的使用不是非常熟悉，于是自己坑了自己，在重载<运算符的时候，搞错了，于是WA了一天。
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
#include<ctime>
#include<climits>
using namespace std;
int pre[505];
int num[505];
int vv[26000],fir[505],nxt[26000],dis[26000];
int maxcost[505],mindis[505];
bool vis[505];
int e;
struct Pnt
{
int mindis,num;
Pnt(int mindis,int num)
{
this->mindis=mindis;
this->num=num;
}
Pnt(){}
bool operator <(const Pnt& b)const
{
return mindis>b.mindis;
}
};
void add(int u,int v,int cost)
{
dis[e]=cost;
vv[e]=v;
nxt[e]=fir[u];
fir[u]=e++;
}
priority_queue<Pnt>que;
vector<int>vec;
int dfs(int sta,int end,int len)
{
vis[sta]=1;
int res=0;
if(sta==end&&!len) res=1;
else if(len<0) res=0;
else
{
for(int i=fir[sta];i!=-1;i=nxt[i])
{
if(!vis[vv[i]])
res+=dfs(vv[i],end,len-dis[i]);
}
}
vis[sta]=0;
return res;
}
int main()
{
int n,m,r1,r2;
while(scanf("%d%d%d%d",&n,&m,&r1,&r2)!=EOF)
{
vec.clear();
e=0;
memset(pre,-1,sizeof(pre));
memset(fir,-1,sizeof(fir));
memset(vis,0,sizeof(vis));
memset(maxcost,-1,sizeof(maxcost));
for(int i=0;i<n;i++)
{
scanf("%d",&num[i]);
mindis[i]=INT_MAX;
}
int u,v,cost;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&cost);
add(u,v,cost);
add(v,u,cost);
}
while(!que.empty()) que.pop();
maxcost[r1]=num[r1];
mindis[r1]=0;
que.push(Pnt(0,r1));
while(!que.empty())
{
Pnt top=que.top();
que.pop();
int number=top.num;
//cout<<"number="<<number<<endl;
if(vis[number]) continue;
vis[number]=1;
for(int i=fir[number];i!=-1;i=nxt[i])
{
int v=vv[i];
//cout<<"v="<<v<<" (number="<<number<<")"<<endl;
if(mindis[v]>mindis[number]+dis[i])
{
mindis[v]=mindis[number]+dis[i];
pre[v]=number;
maxcost[v]=maxcost[number]+num[v];
que.push(Pnt(mindis[v],v));
}
else if(mindis[v]==mindis[number]+dis[i]&&maxcost[v]<num[v]+maxcost[number])
{
pre[v]=number;
maxcost[v]=maxcost[number]+num[v];
que.push(Pnt(mindis[v],v));
}
}
}
memset(vis,0,sizeof(vis));
//count the number
printf("%d %d\n",dfs(r1,r2,mindis[r2]),maxcost[r2]);
//get the route
int tem=r2;
while(tem!=r1)
{
//cout<<"bad\n";
vec.push_back(tem);
tem=pre[tem];
}
vec.push_back(r1);
int size=vec.size();
printf("%d",vec[size-1]);
for(int i=size-2;i>=0;i--)
{
printf(" %d",vec[i]);
}
printf("\n");
}
return 0;
}