1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
|
using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1050; const ll inf=0x3f3f3f3f3f3f3f3fLL; struct { int from,to,dist; }; struct HeapNode{ int d,u; bool operator <(const HeapNode& rhs)const{ return d>rhs.d; } }; struct Dijkstra{ int n,m; vector<Edge>edges; vector<int>G[maxn]; bool done[maxn]; int d[maxn]; int p[maxn];
void init(int n){ this->n=n; for(int i=0;i<n;i++)G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int dist){ edges.push_back((Edge){from,to,dist}); m=edges.size(); G[from].push_back(m-1); } void dijkstra(int s){ priority_queue<HeapNode>Q; for(int i=0;i<n;i++)d[i]=inf; d[s]=0; memset(done,0,sizeof(done)); Q.push((HeapNode){0,s}); while(!Q.empty()){ HeapNode x=Q.top();Q.pop(); int u=x.u; if(done[u])continue; done[u]=true; for(int i=0;i<G[u].size();i++){ Edge& e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist){ d[e.to]=d[u]+e.dist; p[e.to]=G[u][i]; Q.push((HeapNode){d[e.to],e.to}); } } } } void GetShortestPaths(int s,int* dist,vector<int>* paths){ dijkstra(s); for(int i=0;i<n;i++){ dist[i]=d[i]; paths[i].clear(); int t=i; paths[i].push_back(t); while(t!=s){ paths[i].push_back(edges[p[t]].from); t=edges[p[t]].from; } reverse(paths[i].begin(),paths[i].end()); } } };
Dijkstra solver; int d[maxn]; int dp(int u){ if(u==1)return 1; int &ans=d[u]; if(ans>=0)return ans; ans=0; for(int i=0;i<solver.G[u].size();i++){ int v=solver.edges[solver.G[u][i]].to; if(solver.d[v]<solver.d[u])ans+=dp(v); } return ans; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n,m; while(cin>>n){ if(n==0)break; cin>>m; solver.init(n); for(int i=0;i<m;i++){ int a,b,c; cin>>a>>b>>c;a--;b--; solver.AddEdge(a,b,c); solver.AddEdge(b,a,c); } solver.dijkstra(1); memset(d,-1,sizeof(d)); cout<<dp(0)<<endl; } return 0; }
|
近期评论