Sachverhalt:
A.
P._ trat am 1. August 2011 in das von der Stiftung Alters- und Pflegeheim X._ betriebene Heim ein, während ihr Ehemann bis zu dessen Tod im August 2012 in der vormalig gemeinsamen Wohnung in der Stadt Zürich blieb. Mit Einspracheentscheid vom 11. Januar 2013 teilte das Amt für Zusatzleistungen zur AHV/IV der Stadt Zürich der Stiftung Alters- und Pflegeheim X._ mit, es übernehme ab 1. Januar 2013 die Pflegebeiträge für P._ nicht mehr.
B.
Hiegegen erhob die Stiftung Alters- und Pflegeheim X._ Beschwerde beim Sozialversicherungsgericht des Kantons Zürich. Dieses verneinte seine Zuständigkeit und trat auf das Rechtsmittel mit Beschluss vom 31. Mai 2013 nicht ein.
C.
Sowohl die Stiftung Alters- und Pflegeheim X._ (Verfahren 9C_582/2013) als auch die Stadt Zürich, Amt für Zusatzleistungen zur AHV/IV (Verfahren 9C_587/2013), erheben gegen den Nichteintretensbeschluss Beschwerde in öffentlich-rechtlichen Angelegenheiten.
Die Stadt Zürich schliesst sich der Beschwerde der Stiftung Alters- und Pflegeheim X._ an.
D.
Mit Entscheid vom heutigen Tag tritt das Bundesgericht auf die Beschwerde der Stadt Zürich (Verfahren 9C_587/2013) betreffend dieselbe Zuständigkeitsfrage zufolge Verspätung des Rechtsmittels nicht ein.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unter anderem zulässig gegen Entscheide, die das Verfahren abschliessen (<ref-law>). Der vorinstanzliche Nichteintretensentscheid kann als Endentscheid im Sinne von <ref-law> (Urteil 9C_740/2008 vom 10. Oktober 2008 E. 1) oder als - selbstständig eröffneter - Vor- oder Zwischenentscheid über die Zuständigkeit nach <ref-law> betrachtet werden. Die dagegen erhobene Beschwerde in öffentlich-rechtlichen Angelegenheiten ist somit zulässig (<ref-ruling> E. 1 S. 126).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann die Verletzung von Bundesrecht gerügt werden (<ref-law>). Nicht in Art. 95 lit. c-e BGG genannte Quellen kantonalen Rechts werden vom Bundesgericht inhaltlich nur daraufhin überprüft, ob deren Anwendung zu einer Bundesrechtswidrigkeit führt. Im Vordergrund steht dabei eine Verletzung verfassungsmässiger Rechte (<ref-ruling> E. 1 S. 203 mit Hinweisen).
2.
Streitigkeiten nach Eintritt eines Leistungsfalles fallen in die Zuständigkeit der II. sozialrechtlichen Abteilung, wenn - allenfalls auch nur im Hintergrund - sozialversicherungsrechtliche Leistungen umstritten sind. Die kantonale Restfinanzierung der Pflegekosten gehört zu den sozialversicherungsrechtlichen Leistungen. Entsprechende Streitigkeiten fallen somit in die Zuständigkeit der II. sozialrechtlichen Abteilung, wenn, wie hier, ein Leistungsfall bereits eingetreten ist. Auf die Beschwerde kann eingetreten werden (<ref-ruling> E. 2.2 S. 379).
3.
Streitig ist die innerkantonale Zuständigkeit für die Beurteilung von strittiger Restfinanzierung der Pflegekosten gemäss <ref-law>.
3.1. Die Vorinstanz erwog, <ref-law> normiere die Restfinanzierung nicht inhaltlich, sondern sei nur eine Delegationsnorm, welche die Regelungskompetenz den Kantonen übertrage. Diese Kompetenz beinhalte sowohl die Regelung des inner-, wie auch des interkantonalen Verhältnisses, woran nichts ändere, dass die Kantone noch keine umfassende Regelung (Konkordat) erlassen hätten, vielmehr liege darin eine kantonalrechtliche Lücke.
Im Kanton Zürich enthielten weder das kantonale Pflegegesetz vom 27. September 2010 (LS 855.1) noch die Verordnung vom 22. November 2010 über die Pflegeversorgung (LS 855.11) verfahrensrechtliche Bestimmungen zur Restfinanzierung ungedeckter Pflegekosten nach <ref-law>. Das Bundesgesetz vom 6. Oktober 2000 über den Allgemeinen Teil des Sozialversicherungsrechts (ATSG; SR 830.1) werde in der regierungsrätlichen Weisung vom 28. April 2010 zum Pflegegesetz nicht erwähnt. Die Anwendbarkeit des ATSG ergebe sich weder direkt noch gestützt auf die Materialien. Selbst wenn das ATSG mangels kantonaler Verfahrensbestimmungen zu berücksichtigen wäre, käme lediglich eine Anwendung als subsidiäres kantonales Recht in Frage, ohne dass im kantonalen Recht (namentlich nicht im Einführungsgesetz vom 13. Juni 1999 zum Krankenversicherungsgesetz [EG KVG; LS 832.01]) für die Restfinanzierung der Pflegekosten die Zuständigkeit des Sozialversicherungsgerichts des Kantons Zürich statuiert werde. Ebenso wenig ergebe sich dessen Zuständigkeit aus § 3 des Gesetzes vom 7. März 1993 über das Sozialversicherungsgericht (GSVGer; LS 212.81). Die sich auf <ref-law> stützenden kantonalen Vorschriften seien autonomes kantonales Recht. Dass <ref-law> nicht im Ausnahmekatalog von <ref-law> figuriere, lasse nicht darauf schliessen, das ATSG wäre von Bundesrechts wegen auch auf autonomes kantonales Recht anwendbar, das basierend auf <ref-law> ergangen sei. Weil es sich im vorliegenden Fall um einen Streit zwischen einer Pflegeeinrichtung und einer Behörde handle, falle schliesslich die verfahrensrechtliche Erschwerung nicht ins Gewicht, welche bezogen auf natürliche versicherte Personen in <ref-ruling> ein Argument für die Zuständigkeit des kantonalen Versicherungsgerichts gewesen sei.
3.2. Die Beschwerdeführerin bringt vor, <ref-law> sei im Zuge der Neuordnung der Pflegefinanzierung nicht erweitert worden. Das ATSG sei folglich auch im Bereich der Restfinanzierung von Pflegekosten anzuwenden, woran nichts ändere, dass die Leistung nicht durch eine Sozialversicherung erbracht werde. <ref-law> stelle es den Kantonen nicht frei zu legiferieren, sondern belasse ihnen nur in eingeschränktem Mass Regelungskompetenz, namentlich hinsichtlich der Zuständigkeit für die Ausrichtung der Pflegebeiträge, und somit ausschliesslich für den Erlass von Ausführungsbestimmungen. Bei dem <ref-law> umsetzenden kantonalen Recht handle es sich nicht um autonomes kantonales Recht, sondern um unselbstständiges kantonales Ausführungsrecht, welches dem Bundessozialversicherungsrecht zuzuordnen sei. Damit fände das ATSG Anwendung. Im Übrigen sei nicht davon auszugehen, dass der kantonale Gesetzgeber einen von den anderen sozialversicherungsrechtlichen Ansprüchen abweichenden Verfahrensweg im Auge gehabt habe.
3.3. Die Stadt Zürich bringt inhaltlich nichts vor. Sie reicht aber einen - ebenfalls - die innerkantonale Zuständigkeit für die Beurteilung einer Pflegefinanzierungsstreitigkeit betreffenden Entscheid des Verwaltungsgerichts des Kantons Zürich vom 23. Oktober 2013 (Verfahren VB.2013.00200) ins Recht, mit welchem das kantonale Verwaltungsgericht entschied, solche Streitigkeiten fielen in den Zuständigkeitsbereich des kantonalen Sozialversicherungsgerichts, sowie eine Kopie der von ihr gegen den verwaltungsgerichtlichen Entscheid erhobenen Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 21. November 2013 (hängiges Verfahren 9C_849/2013).
4.
4.1. Gemäss <ref-law> ist die Legiferierungskompetenz der Kantone auf die Regelung der Restfinanzierung der Pflegekosten beschränkt. Allein Sache der Bundesgesetzgebung bleibt die abschliessende Normierung der Leistungen der obligatorischen Krankenversicherung. Aber auch der grundsätzliche Anspruch auf Übernahme der ungedeckten Pflegekosten durch die öffentliche Hand (Kanton oder Gemeinden) ist keine Leistung autonomen kantonalen Rechts, sondern ein bundesrechtlicher Anspruch, woran die den Kantonen in <ref-law> übertragene Zuständigkeit nichts ändert (vgl. <ref-ruling> E. 4.2 und 4.3 S. 418 f.). Davon scheint auch der kantonale Gesetzgeber auszugehen, spricht er doch in § 9 Pflegegesetz (Randtitel: "Pflichtleistungen") von der Gesamtheit der Pflegeleistungen gemäss <ref-law>. Diese Gesamtheit der Pflegeleistungen umfasst neben den Leistungen zu Lasten der Versicherer und zu Lasten der Versicherten auch die restlichen Kosten, welche von der Gemeinde zu tragen sind (§ 9 Abs. 4, § 10, § 13 Abs. 3 und § 15 Abs. 2 Pflegegesetz). Ob die kantonale Kompetenz auch das Verfahren umfasst, hat das Bundesgericht in <ref-ruling> E. 5.3 S. 382 offengelassen, unter Hinweis darauf, dass im Bundesgesetz vom 13. Juni 2008 über die Neuordnung der Pflegefinanzierung (AS 2009 3517 ff.) keine explizite Anwendbarkeitserklärung des ATSG erfolgte, weil diese für den Gesetzgeber selbstverständlich war. Auch wenn <ref-law> die Ausnahmen von der Anwendbarkeit des ATSG nicht abschliessend regelt, ist der im Zuge der Neuregelung der Pflegefinanzierung unverändert gebliebene gesetzliche Ausnahmekatalog mindestens ein Indiz, dass für den Gesetzgeber die Anwendbarkeit des ATSG auf Streitigkeiten über die Restfinanzierung evident war. Zum gleichen Schluss gelangte etwa auch der Vorstand der Schweizerischen Konferenz der kantonalen Gesundheitsdirektorinnen und -direktoren (GDK) in seinen am 22. Oktober 2009 verabschiedeten "Empfehlungen zur Umsetzung der Neuordnung der Pflegefinanzierung", worin er die im Rahmen von <ref-law> anerkannten und geleisteten Zahlungen als sozialversicherungsrechtliche Beiträge nach KVG bezeichnete, die in den Anwendungsbereich des ATSG fielen.
4.2. Das Bundesgericht hat in <ref-ruling> E. 5.6 S. 384 f. entschieden, das Verfahren gemäss ATSG finde auf Streitigkeiten über die Restfinanzierung von Pflegeleistungen jedenfalls dann Anwendung, wenn der kantonale Gesetzgeber keine oder keine abweichende Regelung getroffen hat. Daran ist festzuhalten. Während in <ref-ruling>, den Kanton St. Gallen betreffend, keine kantonale Norm vorlag, indes aus den Materialien ein klarer gesetzgeberischer Wille hervorging, wonach es sich bei diesen Streitigkeiten um eine sozialversicherungsrechtliche Leistung handle und demzufolge das ATSG Anwendung finde, ist weder den zürcherischen Normen noch den einschlägigen kantonalen Materialien ein Hinweis auf das anwendbare Verfahrensrecht zu entnehmen. Auch in diesem Fall fehlender kantonaler Grundlagen ist das Verfahren gemäss ATSG anwendbar. Es ist kein Grund ersichtlich, weshalb die kantonalen Versicherungsgerichte für die Beurteilung von Ansprüchen gemäss <ref-law> nicht geeignet sein sollten.
Zudem ist Folgendes zu beachten: Nach dem Gesagten (vorangehende E. 2 und 4.1) sind die Ansprüche auf Übernahme der ungedeckten Pflegekosten sozialversicherungs- sowie bundesrechtlicher Natur. Gemäss <ref-law> finden auf Sozialversicherungsrecht des Bundes die verfahrensrechtlichen Bestimmungen des ATSG Anwendung. Das mit dem ATSG (unter anderem) verfolgte gesetzgeberische Ziel einer Verfahrensvereinheitlichung (<ref-law>) kann nur erreicht werden, wenn das einschlägige Verfahrensrecht möglichst umfassend und - vorbehältlich gesetzlich geregelter Ausnahmen - insbesondere für die Beurteilung bundessozialversicherungsrechtlicher Ansprüche angewendet wird. Nicht zuletzt führte es zu einem wenig wünschbaren, der Maxime der einheitlichen Anwendung des Bundesrechts widersprechenden Zustand, wenn für den gleichen (bundessozialversicherungsrechtlichen) Anspruch in gewissen Kantonen das ATSG als Bundesrecht, in anderen das ATSG als subsidiäres kantonales Recht und wieder in anderen Kantonen das ATSG überhaupt nicht zur Anwendung gelangte. <ref-law> enthält mit Bezug auf das Verfahrensrecht keinen (expliziten) Vorbehalt des Bundesgesetzgebers zu Gunsten des kantonalen Rechts (vielmehr ging der Gesetzgeber wohl selbstverständlich von der Anwendbarkeit des ATSG aus; E. 4.1 hievor).
5.
5.1. Im Kanton Zürich regeln weder das Pflegegesetz noch die zugehörige Verordnung das Verfahren bei Streitigkeiten über die Restfinanzierung von Pflegekosten noch lassen sich den Materialen Hinweise darauf entnehmen, der kantonale Gesetzgeber hätte eine vom ATSG abweichende Verfahrensordnung beabsichtigt (E. 3.1 hievor). Nach dem Gesagten findet damit das ATSG und finden insbesondere dessen Rechtspflegebestimmungen (<ref-law>) Anwendung.
5.2. Nicht zuletzt sprechen auch spezifische kantonalrechtliche Praktikabilitätsgründe für die Anwendbarkeit des ATSG. Die Zuständigkeit für die Restfinanzierung fällt im Kanton Zürich in den kommunalen Kompetenzbereich (§ 21 Abs. 1 Pflegegesetz). Mangels Verfügungskompetenz einer Gemeinde gegenüber einer gemeindefremden öffentlich-rechtlichen oder einer privatrechtlichen Pflegeinstitution wäre die Anfechtung einer abgelehnten Übernahme ungedeckter Pflegebeiträge mittels Rekurs (§ 19 Abs. 1 lit. a in Verbindung mit § 19b Abs. 2 lit. c des kantonalen Verwaltungsrechtspflegegesetzes vom 24. Mai 1959 [VRG; LS 175.2]) in diesen Fällen ausgeschlossen, und es müsste ein Klageverfahren vor Verwaltungsgericht als einziger Instanz angehoben werden (§ 81 lit. a VRG). Dass der kantonale Gesetzgeber für die Pflegefinanzierung unterschiedliche Rechtswege vorsehen wollte, je nachdem, ob sich eine Person in einer gemeindeeigenen öffentlich-rechtlichen Pflegeinstitution oder in einer auswärtigen Pflegeeinrichtung beziehungsweise in einer privatrechtlichen Institution befindet, ist nicht anzunehmen und liegt umso weniger auf der Hand, als das Pflegegesetz in § 9 Abs. 4 und 5 die Tragung der ungedeckten Pflegekosten detailliert regelt, während das Verfahrensrecht keinerlei Erwähnung fand.
5.3. Auf Streitigkeiten betreffend die Pflegefinanzierung zwischen der versicherten Person und dem Kanton gemäss <ref-law> gelangen somit auch im Kanton Zürich die (verfahrensrechtlichen) Bestimmungen des ATSG zur Anwendung. Gemäss dem in <ref-law> vorgezeichneten Rechtsweg ist das kantonale Versicherungsgericht zuständig für die Beurteilung von Streitigkeiten über die Restfinanzierung von Pflegekosten. Die Sache ist an dieses zum materiellen Entscheid zurückzuweisen.
5.4. Anders ist die Rechtslage, wenn es nicht um einen konkreten Leistungsfall geht, sondern um den (grundsätzlichen) Umfang der (kantonalen) Mitfinanzierung von ausserkantonalen Wahlbehandlungen nach <ref-law>. In einem solchen Streitfall handelt es sich um Abgeltung der stationären Leistungen bzw. um die künftige Praxis des Kantons bei der Anerkennung von Forderungen einer stationären Einrichtung. Der Anspruch eines Leistungserbringers gegen den Kanton auf anteilmässige Vergütung der stationären Behandlung lässt sich aus <ref-law> nicht abstrakt, sondern nur anhand eines konkreten Falles ableiten. Damit geht es in der Sache um eine Tarifstreitigkeit zwischen Leistungserbringerin und Kanton, auch wenn Patienten davon indirekt betroffen sein können. Auf diese Streitigkeit sind die Bestimmungen des ATSG nach dem klaren Wortlaut von <ref-law> von vornherein nicht anwendbar. Dies steht im Einklang mit dem Grundsatz, wonach das ATSG primär auf das Verhältnis zwischen Versicherten und Versicherern zugeschnitten ist, und mit <ref-law> diejenigen Bereiche nicht unter das ATSG fallen, für welche das ATSG-Verfahren nicht geeignet ist (9C_905/2013 vom 4. Februar 2014 E. 3.1.2).
6.
Auf die Erhebung von Gerichtskosten wird umständehalber verzichtet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 31. Mai 2013 wird aufgehoben, und die Sache wird an das kantonale Gericht zurückgewiesen, damit es im Sinne der Erwägungen verfahre.
2.
Es werden keine Gerichtskosten erhoben.
3.
Die Beschwerdeführerin wird für das bundesgerichtliche Verfahren mit Fr. 2'800.- aus der Gerichtskasse entschädigt.
4.
Dieses Urteil wird den Parteien, P._, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 18. März 2014
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Die Gerichtsschreiberin: Bollinger Hammerle